Skip to contentSkip to conversation

Yama: remove locking from delete path

PATCH In review Kees Cook 4 participants 9 messages Nov 19, 2012 – Nov 20, 2012

Subsystems (2)
lore
Share & tools
lore

Kees Cook

author
#0 lore raw

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
index 17da6ca..1cba901 100644
@@ -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
maintainer
#1 lore raw
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_free from interrupt context.

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]>
author
#2 lore raw
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_free from interrupt context.

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
maintainer
#3 lore raw
Quoted 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_free from interrupt context.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

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]>
#4 lore raw
In reply to Kees Cook
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_free from interrupt context.

---
 security/yama/yama_lsm.c |   43 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 36 insertions(+), 7 deletions(-)
security/yama/yama_lsm.c +28 -2
index 17da6ca..1cba901 100644
@@ -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 -4
 	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
author
#5 lore raw
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_free from interrupt context.

---
 security/yama/yama_lsm.c |   43 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 36 insertions(+), 7 deletions(-)
security/yama/yama_lsm.c +28 -2
index 17da6ca..1cba901 100644
@@ -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.

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 call schedule_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 -5
      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;
--

1.7.9.5

--
Kees Cook
Chrome OS Security

Signature · 2 lines
Kees Cook
Chrome OS Security
author
#6 lore raw
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_free from interrupt context.

---
 security/yama/yama_lsm.c |   43 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 36 insertions(+), 7 deletions(-)
security/yama/yama_lsm.c +28 -2
index 17da6ca..1cba901 100644
@@ -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.

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 call schedule_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().

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 -5
      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;
--

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
#7 lore raw
In reply to Kees Cook

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_free from 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 ?

author
#8 lore raw
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_free from 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