lockdep trace from posix timers

Quoted 2 lines · Oleg Nesterov

I still think that task_work_add() should synhronize with exit_task_work() itself and fail if necessary. But I wasn't able to convince Al ;)

I'm not at all sure how that relates to needing task_lock() in the keyctl stuff.

Also, can't task_work use llist stuff? That would also avoid using ->pi_lock.

Peter Zijlstra

2012-08-20 11:44 UTC #9 lore raw

Quoted 9 lines · Peter Zijlstra

Quoted 2 lines · Oleg Nesterov
I still think that task_work_add() should synhronize with exit_task_work() itself and fail if necessary. But I wasn't able to convince Al ;)
I'm not at all sure how that relates to needing task_lock() in the keyctl stuff.
Also, can't task_work use llist stuff? That would also avoid using ->pi_lock.

How about something like the below?

---
 include/linux/task_work.h |   7 +--
 kernel/exit.c             |   2 +-
 kernel/task_work.c        | 120 ++++++++++++++++++++++++----------------------
 3 files changed, 65 insertions(+), 64 deletions(-)

include/linux/task_work.h +1 -6

index fb46b03..f365416 100644
@@ -15,11 +15,6 @@ init_task_work(struct callback_head *twork, task_work_func_t func)
 int task_work_add(struct task_struct *task, struct callback_head *twork, bool);
 struct callback_head *task_work_cancel(struct task_struct *, task_work_func_t);
 void task_work_run(void);
-
-static inline void exit_task_work(struct task_struct *task)
-{
-	if (unlikely(task->task_works))
-		task_work_run();
-}
+void task_work_exit(void);
 
 #endif	/* _LINUX_TASK_WORK_H */

kernel/exit.c +1 -1

index f65345f..92aa94b 100644
@@ -992,7 +992,7 @@ void do_exit(long code)
 	exit_shm(tsk);
 	exit_files(tsk);
 	exit_fs(tsk);
-	exit_task_work(tsk);
+	task_work_exit();
 	check_stack_usage();
 	exit_thread();

kernel/task_work.c +63 ~~-57~~

142 lines not on this page · raw message

Peter Zijlstra

2012-08-20 11:47 UTC #10 lore raw

Quoted 2 lines · Peter Zijlstra

Quoted 2 lines
I'm not at all sure how that relates to needing task_lock() in the keyctl stuff.

Ah, is it used to serialize against exit_mm() so that the !->mm check will suffice to avoid queuing works past exit_task_work() ?

Peter Zijlstra

2012-08-20 11:51 UTC #11 lore raw

kernel/task_work.c line 20

Quoted 7 lines · Peter Zijlstra

int

kernel/task_work.c +5 -0

+task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
+       struct callback_head **head = &task->task_works;
+       struct callback_head *entry, *old_entry;
+
+       entry = &head;

My compiler just alerted me that:

	entry = *head;

works a lot better..

Quoted 17 lines

kernel/task_work.c +11 -0

+       for (;;) {
+               if (entry == &dead)
+                       return -ESRCH;
+
+               old_entry = entry;
+               work->next = entry;
+               entry = cmpxchg(head, old_entry, work);
+               if (entry == old_entry)
+                       break;
+       }
 
        /* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
        if (notify)
                set_notify_resume(task);
+
        return 0;
 }

Steven Rostedt

2012-08-20 12:19 UTC #12 lore raw

Quoted 11 lines · Peter Zijlstra

kernel/task_work.c line 20
Quoted 7 lines · Peter Zijlstra
int
kernel/task_work.c +5 -0
+task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
+       struct callback_head **head = &task->task_works;
+       struct callback_head *entry, *old_entry;
+
+       entry = &head;
My compiler just alerted me that:

Quoted 6 lines

	entry = *head;

works a lot better..

Quoted 2 lines

kernel/task_work.c +2 -0

+       for (;;) {
+               if (entry == &dead)

But your compiler likes "entry == &dead"? ;-)

-- Steve

Quoted 15 lines

kernel/task_work.c +9 -0

+                       return -ESRCH;
+
+               old_entry = entry;
+               work->next = entry;
+               entry = cmpxchg(head, old_entry, work);
+               if (entry == old_entry)
+                       break;
+       }
 
        /* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
        if (notify)
                set_notify_resume(task);
+
        return 0;
 }

Peter Zijlstra

2012-08-20 12:20 UTC #13 lore raw

Quoted 6 lines · Steven Rostedt

Quoted 3 lines
kernel/task_work.c line 22
Quoted 3 lines
kernel/task_work.c +2 -0
+       for (;;) {
+               if (entry == &dead)
But your compiler likes "entry == &dead"? ;-)

Yes, fancy as GCC is these days, it doesn't quite bother with the meta-physical questions just yet.

Oleg Nesterov

2012-08-20 15:02 UTC #14 lore raw

kernel/task_work.c line 48

Quoted 10 lines · Peter Zijlstra

task_work_cancel(struct task_struct *task, task_work_func_t func) {
...
kernel/task_work.c +6 -0
+
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {

But this all can race with task_work_run() if task != current.

This "work" can be freed/reused. And it should only return !NULL if twork->func() was not called.

Oleg.

Peter Zijlstra

2012-08-20 15:10 UTC #15 lore raw

Quoted 14 lines · Oleg Nesterov

kernel/task_work.c line 48
Quoted 10 lines · Peter Zijlstra
task_work_cancel(struct task_struct *task, task_work_func_t func) {
...
kernel/task_work.c +6 -0
+
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {
But this all can race with task_work_run() if task != current.

Quoted 2 lines

This "work" can be freed/reused. And it should only return !NULL if twork->func() was not called.

Ah, because we could be iterating the list after the xchg done by run.

Hmm..

Peter Zijlstra

2012-08-20 15:27 UTC #16 lore raw

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Oleg Nesterov
kernel/task_work.c line 48
Quoted 10 lines · Peter Zijlstra
task_work_cancel(struct task_struct *task, task_work_func_t func) {
...
kernel/task_work.c +6 -0
+
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {
But this all can race with task_work_run() if task != current.

Quoted 4 lines

Quoted 2 lines
This "work" can be freed/reused. And it should only return !NULL if twork->func() was not called.
Ah, because we could be iterating the list after the xchg done by run.

I guess we could steal the entire list and requeue it afterwards and lift TIF_NOTIFY_RESUME along with it.. but I can't say that's pretty.

Oleg Nesterov

2012-08-20 15:36 UTC #17 lore raw

Quoted 17 lines · Peter Zijlstra

Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Oleg Nesterov
kernel/task_work.c line 48
Quoted 10 lines · Peter Zijlstra
task_work_cancel(struct task_struct *task, task_work_func_t func) {
...
kernel/task_work.c +6 -0
+
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {
But this all can race with task_work_run() if task != current.

Quoted 7 lines

Quoted 4 lines
Quoted 2 lines
This "work" can be freed/reused. And it should only return !NULL if twork->func() was not called.
Ah, because we could be iterating the list after the xchg done by run.
I guess we could steal the entire list and requeue it afterwards and lift TIF_NOTIFY_RESUME along with it..

We can't. This can race with exit_task_work(). And this can break fput(), the task can return to the userspace without __fput().

Quoted 1 line

but I can't say that's pretty.

Yes ;)

Oleg.

Peter Zijlstra

2012-08-20 15:47 UTC #18 lore raw

Quoted 5 lines · Oleg Nesterov

Quoted 2 lines
I guess we could steal the entire list and requeue it afterwards and lift TIF_NOTIFY_RESUME along with it..
We can't. This can race with exit_task_work(). And this can break fput(), the task can return to the userspace without __fput().

So we could put that spinlock back around cancel and run and leave add lockless. That'd solve my immediate problem but its not something I'm proud of.

All schemes I can come up with end up being broken or effectively the same as the above proposal.

Oleg Nesterov

2012-08-20 16:01 UTC #19 lore raw

Quoted 6 lines · Peter Zijlstra

Quoted 3 lines · Oleg Nesterov
Quoted 2 lines
I guess we could steal the entire list and requeue it afterwards and lift TIF_NOTIFY_RESUME along with it..

Quoted 6 lines

Quoted 2 lines
We can't. This can race with exit_task_work(). And this can break fput(), the task can return to the userspace without __fput().
So we could put that spinlock back around cancel and run and leave add lockless. That'd solve my immediate problem but its not something I'm proud of.

Which problem?

We can probably use bit_spin_lock() and avoid ->pi_lock.

Of course, we can add the new lock into task_struct, but this is not nice.

Oleg.

Peter Zijlstra

2012-08-20 16:03 UTC #20 lore raw

Quoted 7 lines · Oleg Nesterov

Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Oleg Nesterov
Quoted 2 lines
I guess we could steal the entire list and requeue it afterwards and lift TIF_NOTIFY_RESUME along with it..

Quoted 8 lines

Quoted 6 lines
Quoted 2 lines
We can't. This can race with exit_task_work(). And this can break fput(), the task can return to the userspace without __fput().
So we could put that spinlock back around cancel and run and leave add lockless. That'd solve my immediate problem but its not something I'm proud of.
Which problem?

/me doing task_work_add() from under rq->lock..

Quoted 1 line

We can probably use bit_spin_lock() and avoid ->pi_lock.

tglx will kill us both for even thinking of bit-spinlocks.

Quoted 1 line

Of course, we can add the new lock into task_struct, but this is not nice.

If we can limit the lock to cancel/run I'm ok.

Oleg Nesterov

2012-08-20 15:08 UTC #21 lore raw

Quoted 25 lines · Peter Zijlstra

kernel/task_work.c +5 ~~-18~~

+static void __task_work_run(struct callback_head *tail)
 {
-	struct task_struct *task = current;
-	struct callback_head *p, *q;
-
-	while (1) {
-		raw_spin_lock_irq(&task->pi_lock);
-		p = task->task_works;
-		task->task_works = NULL;
-		raw_spin_unlock_irq(&task->pi_lock);
-
-		if (unlikely(!p))
-			return;
-
-		q = p->next; /* head */
-		p->next = NULL; /* cut it */
-		while (q) {
-			p = q->next;
-			q->func(q);
-			q = p;
+	struct callback_head **head = &current->task_works;
+
+	do {
+		struct callback_head *work = xchg(head, NULL);

kernel/task_work.c line 75

Quoted 10 lines

kernel/task_work.c +8 -1

+		while (work) {
+			struct callback_head *next = ACCESS_ONCE(work->next);
+
+			WARN_ON_ONCE(work == &dead);
+
+			work->func(work);
+			work = next;
 		}
-	}
+	} while (cmpxchg(head, NULL, tail) != NULL);

Yes, we can add the explicit argument to __task_work_run(), but it can check PF_EXITING instead, this looks simpler to me.

Note also your patch breaks fifo, but this is fixable.

Oleg.

Peter Zijlstra

2012-08-20 15:12 UTC #22 lore raw

Quoted 31 lines · Oleg Nesterov

Quoted 30 lines · Peter Zijlstra

kernel/task_work.c +10 ~~-18~~

+static void __task_work_run(struct callback_head *tail)
 {
-	struct task_struct *task = current;
-	struct callback_head *p, *q;
-
-	while (1) {
-		raw_spin_lock_irq(&task->pi_lock);
-		p = task->task_works;
-		task->task_works = NULL;
-		raw_spin_unlock_irq(&task->pi_lock);
-
-		if (unlikely(!p))
-			return;
-
-		q = p->next; /* head */
-		p->next = NULL; /* cut it */
-		while (q) {
-			p = q->next;
-			q->func(q);
-			q = p;
+	struct callback_head **head = &current->task_works;
+
+	do {
+		struct callback_head *work = xchg(head, NULL);
+		while (work) {
+			struct callback_head *next = ACCESS_ONCE(work->next);
+
+			WARN_ON_ONCE(work == &dead);
+

Quoted 8 lines

kernel/task_work.c line 75
Quoted 5 lines
kernel/task_work.c +3 -1
+			work->func(work);
+			work = next;
 		}
-	}
+	} while (cmpxchg(head, NULL, tail) != NULL);
Yes, we can add the explicit argument to __task_work_run(), but it can check PF_EXITING instead, this looks simpler to me.

I guess we could.. but I thought the explicit callback was simpler ;-)

Quoted 1 line

Note also your patch breaks fifo, but this is fixable.

Why do you care about the order? Iterating a single linked queue in fifo seems more expensive than useful.

Oleg Nesterov

2012-08-20 15:45 UTC #23 lore raw

Quoted 7 lines · Peter Zijlstra

Quoted 3 lines · Oleg Nesterov
Yes, we can add the explicit argument to __task_work_run(), but it can check PF_EXITING instead, this looks simpler to me.
I guess we could.. but I thought the explicit callback was simpler ;-)

I won't insist. The patch I sent uses PF_EXITING and the fake "struct callback_head* TWORK_EXITED", but this looks almost the same.

Quoted 3 lines

Quoted 1 line
Note also your patch breaks fifo, but this is fixable.
Why do you care about the order?

IMHO, this is just more natural.

For example. keyctl_session_to_parent() does _cancel only to protect from exploits doing keyctl(KEYCTL_SESSION_TO_PARENT) in an endless loop. It could simply do task_work_add(), but in this case we need fifo for correctness.

Quoted 2 lines

Iterating a single linked queue in fifo
seems more expensive than useful.

Currently the list is fifo (we add to the last element), this is O(1).

But the list should be short, we can reverse it in _run() if we change task_work_add() to add to the head.

Oleg.

Peter Zijlstra

2012-08-20 15:57 UTC #24 lore raw

Quoted 2 lines · Oleg Nesterov

I won't insist. The patch I sent uses PF_EXITING and the fake "struct callback_head* TWORK_EXITED", but this looks almost the same.

Right, I used a fake callback_head because it avoided a few special cases since its a dereferencable pointer.

Quoted 5 lines

Quoted 3 lines
Quoted 1 line
Note also your patch breaks fifo, but this is fixable.
Why do you care about the order?
IMHO, this is just more natural.

Depends on what you're used to I guess ;-) Both RCU and irq_work are filo, this seems to be the natural way for single linked lists.

Quoted 4 lines

For example. keyctl_session_to_parent() does _cancel only to protect from exploits doing keyctl(KEYCTL_SESSION_TO_PARENT) in an endless loop. It could simply do task_work_add(), but in this case we need fifo for correctness.

I'm not entirely sure I see, not doing the cancel would delay the free until the executing of key_change_session_keyring()? doing that keyctl() in an indefinite loop involves going back to userspace, so where's the resource issue?

Also, I'm not seeing where the FIFO requirement comes from.

Quoted 4 lines

Quoted 2 lines
Iterating a single linked queue in fifo
seems more expensive than useful.
Currently the list is fifo (we add to the last element), this is O(1).

depends on what way you look at the list I guess, with a single linked list there's only one end you can add to in O(1), so we're calling that the tail?

Quoted 2 lines

But the list should be short, we can reverse it in _run() if we change task_work_add() to add to the head.

Reversing a (single linked) list is O(n^2).. which is indeed doable for short lists, but why assume its short?

Oleg Nesterov

2012-08-20 16:13 UTC #25 lore raw

Quoted 6 lines · Peter Zijlstra

Quoted 1 line · Oleg Nesterov
IMHO, this is just more natural.
Depends on what you're used to I guess ;-)

I have to agree ;)

Quoted 9 lines

Quoted 4 lines
For example. keyctl_session_to_parent() does _cancel only to protect from exploits doing keyctl(KEYCTL_SESSION_TO_PARENT) in an endless loop. It could simply do task_work_add(), but in this case we need fifo for correctness.
I'm not entirely sure I see, not doing the cancel would delay the free until the executing of key_change_session_keyring()? doing that keyctl() in an indefinite loop involves going back to userspace, so where's the resource issue?

But the child does task_work_add(current->parent). IOW, there are 2 different tasks. Now suppose that ->parent sleeps.

Quoted 1 line

Also, I'm not seeing where the FIFO requirement comes from.

Again, suppose that ->parent sleeps. The last KEYCTL_SESSION_TO_PARENT request should "win". Although I agree, this is not that important.

Quoted 8 lines

Quoted 4 lines
Quoted 2 lines
Iterating a single linked queue in fifo
seems more expensive than useful.
Currently the list is fifo (we add to the last element), this is O(1).
depends on what way you look at the list I guess, with a single linked list there's only one end you can add to in O(1), so we're calling that the tail?

Sorry, can't understand...

task->task_works points to the last node in the circular single-linked list, task_work_add() adds the new element after the last one and updates task->task_works. This is O(1).

Quoted 4 lines

Quoted 2 lines
But the list should be short, we can reverse it in _run() if we change task_work_add() to add to the head.
Reversing a (single linked) list is O(n^2)..

Hmm. This is O(n). You can simply iterate over this list once, changing the ->next pointer to point back.

Quoted 2 lines

which is indeed doable for
short lists, but why assume its short?

I agree, it is better to not do this.

Oleg.

Peter Zijlstra

2012-08-20 16:20 UTC #26 lore raw

Quoted 3 lines · Oleg Nesterov

task->task_works points to the last node in the circular single-linked list, task_work_add() adds the new element after the last one and updates task->task_works. This is O(1).

Agreed, the way I was looking at that is: ->task_works points to the head and we put a new one in front, that too is O(1) ;-)

Quoted 7 lines

Quoted 4 lines
Quoted 2 lines
But the list should be short, we can reverse it in _run() if we change task_work_add() to add to the head.
Reversing a (single linked) list is O(n^2)..
Hmm. This is O(n). You can simply iterate over this list once, changing the ->next pointer to point back.

OK, I'm going to stop and step away from the computer now.. clearly I more than useless today :/

But yeah.. that could be done.

Anyway, would taking ->pi_lock over _cancel and _run suffice?

Oleg Nesterov

2012-08-20 16:26 UTC #27 lore raw

Quoted 2 lines · Peter Zijlstra

Anyway, would taking ->pi_lock over _cancel and _run suffice?

I thinks yes... But I can't think properly today.

Oleg.

Oleg Nesterov

2012-08-21 18:31 UTC #28 lore raw

Quoted 6 lines · Oleg Nesterov

Quoted 2 lines · Peter Zijlstra
Anyway, would taking ->pi_lock over _cancel and _run suffice?
I thinks yes... But I can't think properly today.

OK, how about the code below?

Oleg.

#define TWORK_EXITED ((struct callback_head*)1)

static inline bool cmp_xchg(struct callback_head **ptr, void *old, void *new)

{
	return cmpxchg(ptr, old, new) == old;
}

int
task_work_add(struct task_struct *task, struct callback_head *twork, bool notify)

{
	do {
		twork->next = ACCESS_ONCE(task->task_works);
		if (unlikely(twork->next == TWORK_EXITED))
			return -ESRCH;
	} while (cmp_xchg(&task->task_works, twork->next, twork));

	/* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
	if (notify)
		set_notify_resume(task);
	return 0;
}

struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func)

{
	struct callback_head *twork = NULL, **pprev = &task->task_works;
	unsigned long flags;

	raw_spin_lock_irqsave(&task->pi_lock, flags);
	if (likely(*pprev != TWORK_EXITED)) {
		for (; (twork = *pprev); pprev = &twork) {
			read_barrier_depends();
			if (twork->func != func)
				continue;

			while (!cmp_xchg(pprev, twork, twork->next))
				// COMMENT ABOUT THE RACE WITH _add()
				pprev = &(*pprev)->next;
			break;
		}
	}
	raw_spin_unlock_irqrestore(&task->pi_lock, flags);

	return twork;
}

void task_work_run(void)

{
	struct task_struct *task = current;
	struct callback_head *twork, *marker;

	for (;;) {
		raw_spin_lock_irq(&task->pi_lock);
		do {
			twork = ACCESS_ONCE(task->task_works);
			marker = (!twork && (task->flags & PF_EXITING)) ?
				TWORK_EXITED : NULL;
		} while (cmp_xchg(&task->task_works, twork, marker));
		raw_spin_unlock_irq(&task->pi_lock);

		if (!twork)
			break;

		...run works...
	}
}

Oleg Nesterov

2012-08-21 18:37 UTC #29 lore raw

Quoted 6 lines · Oleg Nesterov

static inline bool cmp_xchg(struct callback_head **ptr, void *old, void *new)
{
	return cmpxchg(ptr, old, new) == old;
}

Quoted 8 lines

int
task_work_add(struct task_struct *task, struct callback_head *twork, bool notify)
{
	do {
		twork->next = ACCESS_ONCE(task->task_works);
		if (unlikely(twork->next == TWORK_EXITED))
			return -ESRCH;
	} while (cmp_xchg(&task->task_works, twork->next, twork));

          ^^^^^^^^^^^^^^^

while (!cmp_xchg(...))

Oleg.

Oleg Nesterov

2012-08-24 18:54 UTC #30 lore raw

Quoted 11 lines · Oleg Nesterov

Quoted 8 lines
task_work_add(struct task_struct *task, struct callback_head *twork, bool notify)
{
	do {
		twork->next = ACCESS_ONCE(task->task_works);
		if (unlikely(twork->next == TWORK_EXITED))
			return -ESRCH;
	} while (cmp_xchg(&task->task_works, twork->next, twork));
          ^^^^^^^^^^^^^^^
while (!cmp_xchg(...))

and _cancel can be simplified a bit.

OK, I actually tested the code below, seems to work.

Peter, if you think it can work for you and if you agree with the implementation I will be happy to send the patch.

The only change outside of task_work.c is that exit_task_work() should call task_work_run() unconditionally.

As for cmp_xchg below... Of course it is not strictly needed. But otoh, personally I'd like to have this helper (probably renamed) somewhere in include/linux. Perhaps this is just me, but cmpxchg() always confuses me, and most users only need success_or_not from cmpxchg.

Oleg.

#define cmp_xchg(ptr, _old, new) \

({					\
	__typeof__(_old) old = (_old);	\
	cmpxchg(ptr, old, new) == old;	\
})

#define TWORK_EXITED ((struct callback_head*)1)

int
task_work_add(struct task_struct *task, struct callback_head *work, bool notify)

{
	do {
		work->next = ACCESS_ONCE(task->task_works);
		if (unlikely(work->next == TWORK_EXITED))
			return -ESRCH;
	} while (!cmp_xchg(&task->task_works, work->next, work));

	/* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
	if (notify)
		set_notify_resume(task);
	return 0;
}

struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func)

{
	struct callback_head **pprev = &task->task_works;
	struct callback_head *work = NULL;
	unsigned long flags;

	raw_spin_lock_irqsave(&task->pi_lock, flags);
	if (likely(*pprev != TWORK_EXITED)) {
		while ((work = *pprev)) {
			read_barrier_depends();
			if (work->func != func)
				pprev = &work->next;
			else if (cmp_xchg(pprev, work, work->next))
				break;
		}
	}
	raw_spin_unlock_irqrestore(&task->pi_lock, flags);

	return work;
}

void task_work_run(void)

{
	struct task_struct *task = current;
	struct callback_head *work, *head, *next;

	for (;;) {
		raw_spin_lock_irq(&task->pi_lock);
		do {
			work = ACCESS_ONCE(task->task_works);
			head = !work && (task->flags & PF_EXITING) ?
				TWORK_EXITED : NULL;
		} while (!cmp_xchg(&task->task_works, work, head));
		raw_spin_unlock_irq(&task->pi_lock);

		if (!work)
			break;

#if PETERZ_WONT_ARGUE_AGAINST_FIFO_TOO_MUCH
		head = NULL;
		do {
			next = work->next;
			work->next = head;
			head = work;
			work = next;
		} while (work);

		work = head;
#endif
		do {
			next = work->next;
			work->func(work);
			work = next;
			cond_resched();
		} while (work);
	}
}

Oleg Nesterov

2012-08-26 19:09 UTC #31 lore raw

cover (Was: lockdep trace from posix timers)

Quoted 3 lines · Oleg Nesterov

Peter, if you think it can work for you and if you agree with the implementation I will be happy to send the patch.

I think I should try anyway ;)

To simplify the review, I attached the resulting code below.

Changes:

- Comments.

- Not sure this is really better, but task_work_run() does not need to actually take pi_lock, unlock_wait is enough.

However, in this case the dummy entry is better than the fake pointer.

Oleg.

#include <linux/spinlock.h>
#include <linux/task_work.h>
#include <linux/tracehook.h>

static struct callback_head work_exited; /* all we need is ->next == NULL */

int
task_work_add(struct task_struct *task, struct callback_head *work, bool notify)

{
	struct callback_head *head;

	do {
		head = ACCESS_ONCE(task->task_works);
		if (unlikely(head == &work_exited))
			return -ESRCH;
		work->next = head;
	} while (cmpxchg(&task->task_works, head, work) != head);

	if (notify)
		set_notify_resume(task);
	return 0;
}

struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func)

{
	struct callback_head **pprev = &task->task_works;
	struct callback_head *work = NULL;
	unsigned long flags;
	/*
	 * If cmpxchg() fails we continue without updating pprev.
	 * Either we raced with task_work_add() which added the
	 * new entry before this work, we will find it again. Or
	 * we raced with task_work_run(), *pprev == NULL/exited.
	 */
	raw_spin_lock_irqsave(&task->pi_lock, flags);
	while ((work = ACCESS_ONCE(*pprev))) {
		read_barrier_depends();
		if (work->func != func)
			pprev = &work->next;
		else if (cmpxchg(pprev, work, work->next) == work)
			break;
	}
	raw_spin_unlock_irqrestore(&task->pi_lock, flags);

	return work;
}

void task_work_run(void)

{
	struct task_struct *task = current;
	struct callback_head *work, *head, *next;

	for (;;) {
		/*
		 * work->func() can do task_work_add(), do not set
		 * work_exited unless the list is empty.
		 */
		do {
			work = ACCESS_ONCE(task->task_works);
			head = !work && (task->flags & PF_EXITING) ?
				&work_exited : NULL;
		} while (cmpxchg(&task->task_works, work, head) != work);

		if (!work)
			break;
		/*
		 * Synchronize with task_work_cancel(). It can't remove
		 * the first entry == work, cmpxchg(task_works) should
		 * fail, but it can play with *work and other entries.
		 */
		raw_spin_unlock_wait(&task->pi_lock);
		smp_mb();

		/* Reverse the list to run the works in fifo order */
		head = NULL;
		do {
			next = work->next;
			work->next = head;
			head = work;
			work = next;
		} while (work);

		work = head;
		do {
			next = work->next;
			work->func(work);
			work = next;
			cond_resched();
		} while (work);
	}
}

Oleg Nesterov

2012-08-26 19:10 UTC #32 lore raw

PATCH 1/4 task_work: make task_work_add() lockless

Change task_works to use llist-like code to avoid pi_lock in task_work_add(), this makes it useable under rq->lock.

task_work_cancel() and task_work_run() still use pi_lock to synchronize with each other.

---
 kernel/task_work.c |   95 ++++++++++++++++++++++++++-------------------------
 1 files changed, 48 insertions(+), 47 deletions(-)

kernel/task_work.c +48 ~~-47~~

index d320d44..f13ec0b 100644
@@ -3,25 +3,18 @@
 #include <linux/tracehook.h>
 
 int
-task_work_add(struct task_struct *task, struct callback_head *twork, bool notify)
+task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
-	struct callback_head *last, *first;
-	unsigned long flags;
-
+	struct callback_head *head;
 	/*
 	 * Not inserting the new work if the task has already passed
 	 * exit_task_work() is the responisbility of callers.
 	 */
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	last = task->task_works;
-	first = last ? last->next : twork;
-	twork->next = first;
-	if (last)
-		last->next = twork;
-	task->task_works = twork;
-	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	do {
+		head = ACCESS_ONCE(task->task_works);
+		work->next = head;
+	} while (cmpxchg(&task->task_works, head, work) != head);
 
-	/* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
 	if (notify)
 		set_notify_resume(task);
 	return 0;

@@ -30,52 +23,60 @@ task_work_add(struct task_struct *task, struct callback_head *twork, bool notify
 struct callback_head *
 task_work_cancel(struct task_struct *task, task_work_func_t func)
 {
+	struct callback_head **pprev = &task->task_works;
+	struct callback_head *work = NULL;
 	unsigned long flags;
-	struct callback_head *last, *res = NULL;
-
+	/*
+	 * If cmpxchg() fails we continue without updating pprev.
+	 * Either we raced with task_work_add() which added the
+	 * new entry before this work, we will find it again. Or
+	 * we raced with task_work_run(), *pprev == NULL.
+	 */
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	last = task->task_works;
-	if (last) {
-		struct callback_head *q = last, *p = q->next;
-		while (1) {
-			if (p->func == func) {
-				q->next = p->next;
-				if (p == last)
-					task->task_works = q == p ? NULL : q;
-				res = p;
-				break;
-			}
-			if (p == last)
-				break;
-			q = p;
-			p = q->next;
-		}
+	while ((work = ACCESS_ONCE(*pprev))) {
+		read_barrier_depends();
+		if (work->func != func)
+			pprev = &work->next;
+		else if (cmpxchg(pprev, work, work->next) == work)
+			break;
 	}
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-	return res;
+
+	return work;
 }
 
 void task_work_run(void)
 {
 	struct task_struct *task = current;
-	struct callback_head *p, *q;
+	struct callback_head *work, *head, *next;
 
-	while (1) {
-		raw_spin_lock_irq(&task->pi_lock);
-		p = task->task_works;
-		task->task_works = NULL;
-		raw_spin_unlock_irq(&task->pi_lock);
+	for (;;) {
+		work = xchg(&task->task_works, NULL);
+		if (!work)
+			break;
+		/*
+		 * Synchronize with task_work_cancel(). It can't remove
+		 * the first entry == work, cmpxchg(task_works) should
+		 * fail, but it can play with *work and other entries.
+		 */
+		raw_spin_unlock_wait(&task->pi_lock);
+		smp_mb();
 
-		if (unlikely(!p))
-			return;
+		/* Reverse the list to run the works in fifo order */
+		head = NULL;
+		do {
+			next = work->next;
+			work->next = head;
+			head = work;
+			work = next;
+		} while (work);
 
-		q = p->next; /* head */
-		p->next = NULL; /* cut it */
-		while (q) {
-			p = q->next;
-			q->func(q);
-			q = p;
+		work = head;
+		do {
+			next = work->next;
+			work->func(work);
+			work = next;
 			cond_resched();
-		}
+		} while (work);
 	}
 }

Signature · 1 line

1.5.5.1

tip-bot for Oleg Nesterov

2012-09-14 06:08 UTC #33 lore raw

[tip:core/urgent] task_work: Make task_work_add() lockless

Commit-ID:  ac3d0da8f3290b3d394cdb7f50604424a7cd6092
Gitweb:     http://git.kernel.org/tip/ac3d0da8f3290b3d394cdb7f50604424a7cd6092
Author:     Oleg Nesterov <[email protected]>
AuthorDate: Sun, 26 Aug 2012 21:12:09 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 13 Sep 2012 16:47:33 +0200

task_work: Make task_work_add() lockless

Change task_work's to use llist-like code to avoid pi_lock in task_work_add(), this makes it useable under rq->lock.

task_work_cancel() and task_work_run() still use pi_lock to synchronize with each other.

(This is in preparation for a deadlock fix.)

Cc Al Viro <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Thomas Gleixner <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/task_work.c |   95 ++++++++++++++++++++++++++-------------------------
 1 files changed, 48 insertions(+), 47 deletions(-)

kernel/task_work.c +48 ~~-47~~

index d320d44..f13ec0b 100644
@@ -3,25 +3,18 @@
 #include <linux/tracehook.h>
 
 int
-task_work_add(struct task_struct *task, struct callback_head *twork, bool notify)
+task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
-	struct callback_head *last, *first;
-	unsigned long flags;
-
+	struct callback_head *head;
 	/*
 	 * Not inserting the new work if the task has already passed
 	 * exit_task_work() is the responisbility of callers.
 	 */
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	last = task->task_works;
-	first = last ? last->next : twork;
-	twork->next = first;
-	if (last)
-		last->next = twork;
-	task->task_works = twork;
-	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
+	do {
+		head = ACCESS_ONCE(task->task_works);
+		work->next = head;
+	} while (cmpxchg(&task->task_works, head, work) != head);
 
-	/* test_and_set_bit() implies mb(), see tracehook_notify_resume(). */
 	if (notify)
 		set_notify_resume(task);
 	return 0;

@@ -30,52 +23,60 @@ task_work_add(struct task_struct *task, struct callback_head *twork, bool notify
 struct callback_head *
 task_work_cancel(struct task_struct *task, task_work_func_t func)
 {
+	struct callback_head **pprev = &task->task_works;
+	struct callback_head *work = NULL;
 	unsigned long flags;
-	struct callback_head *last, *res = NULL;
-
+	/*
+	 * If cmpxchg() fails we continue without updating pprev.
+	 * Either we raced with task_work_add() which added the
+	 * new entry before this work, we will find it again. Or
+	 * we raced with task_work_run(), *pprev == NULL.
+	 */
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	last = task->task_works;
-	if (last) {
-		struct callback_head *q = last, *p = q->next;
-		while (1) {
-			if (p->func == func) {
-				q->next = p->next;
-				if (p == last)
-					task->task_works = q == p ? NULL : q;
-				res = p;
-				break;
-			}
-			if (p == last)
-				break;
-			q = p;
-			p = q->next;
-		}
+	while ((work = ACCESS_ONCE(*pprev))) {
+		read_barrier_depends();
+		if (work->func != func)
+			pprev = &work->next;
+		else if (cmpxchg(pprev, work, work->next) == work)
+			break;
 	}
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-	return res;
+
+	return work;
 }
 
 void task_work_run(void)
 {
 	struct task_struct *task = current;
-	struct callback_head *p, *q;
+	struct callback_head *work, *head, *next;
 
-	while (1) {
-		raw_spin_lock_irq(&task->pi_lock);
-		p = task->task_works;
-		task->task_works = NULL;
-		raw_spin_unlock_irq(&task->pi_lock);
+	for (;;) {
+		work = xchg(&task->task_works, NULL);
+		if (!work)
+			break;
+		/*
+		 * Synchronize with task_work_cancel(). It can't remove
+		 * the first entry == work, cmpxchg(task_works) should
+		 * fail, but it can play with *work and other entries.
+		 */
+		raw_spin_unlock_wait(&task->pi_lock);
+		smp_mb();
 
-		if (unlikely(!p))
-			return;
+		/* Reverse the list to run the works in fifo order */
+		head = NULL;
+		do {
+			next = work->next;
+			work->next = head;
+			head = work;
+			work = next;
+		} while (work);
 
-		q = p->next; /* head */
-		p->next = NULL; /* cut it */
-		while (q) {
-			p = q->next;
-			q->func(q);
-			q = p;
+		work = head;
+		do {
+			next = work->next;
+			work->func(work);
+			work = next;
 			cond_resched();
-		}
+		} while (work);
 	}
 }

Geert Uytterhoeven

2012-09-24 19:27 UTC #34 lore raw

Re: [PATCH 1/4] task_work: make task_work_add() lockless

Quoted 36 lines · Oleg Nesterov

Change task_works to use llist-like code to avoid pi_lock in task_work_add(), this makes it useable under rq->lock.

task_work_cancel() and task_work_run() still use pi_lock to synchronize with each other.

http://kisskb.ellerman.id.au/kisskb/buildresult/7238385/

kernel/task_work.c +8 ~~-10~~

@@ -30,52 +23,60 @@ task_work_add(struct task_struct *task, struct callback_head *twork, bool notify
 struct callback_head *
 task_work_cancel(struct task_struct *task, task_work_func_t func)
 {
+       struct callback_head **pprev = &task->task_works;
+       struct callback_head *work = NULL;
        unsigned long flags;
-       struct callback_head *last, *res = NULL;
-
+       /*
+        * If cmpxchg() fails we continue without updating pprev.
+        * Either we raced with task_work_add() which added the
+        * new entry before this work, we will find it again. Or
+        * we raced with task_work_run(), *pprev == NULL.
+        */
        raw_spin_lock_irqsave(&task->pi_lock, flags);
-       last = task->task_works;
-       if (last) {
-               struct callback_head *q = last, *p = q->next;
-               while (1) {
-                       if (p->func == func) {
-                               q->next = p->next;
-                               if (p == last)
-                                       task->task_works = q == p ? NULL : q;

kernel/task_work.c task_work_add(struct task_struct *task, struct callback_head *twork, bool notify · line 37

Quoted 10 lines

kernel/task_work.c +2 -8

-                               res = p;
-                               break;
-                       }
-                       if (p == last)
-                               break;
-                       q = p;
-                       p = q->next;
-               }
+       while ((work = ACCESS_ONCE(*pprev))) {
+               read_barrier_depends();

Woops, h8300 doesn't have read_barrier_depends():
kernel/task_work.c:38:3: error: implicit declaration of function 'read_barrier_depends' [-Werror=implicit-function-declaration]
cc1: some warnings being treated as errors
make[2]: *** [kernel/task_work.o] Error 1

Perhaps an empty definition is fine? Most architectures have:

#define read_barrier_depends() do { } while(0)

The same issue on c6x just got fixed in -next in commit 2c8c2366077da5645bf9063b3cf5c94ecb16f691 ("c6x: use asm-generic/barrier.h")

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

Oleg Nesterov

2012-09-24 20:36 UTC #35 lore raw

Re: [PATCH 1/4] task_work: make task_work_add() lockless

Quoted 4 lines · Geert Uytterhoeven

kernel/task_work.c task_work_add(struct task_struct *task, struct callback_head *twork, bool notify · line 37
Quoted 2 lines · Oleg Nesterov
kernel/task_work.c +2 -0
+       while ((work = ACCESS_ONCE(*pprev))) {
+               read_barrier_depends();

Hmm. This should be smp_read_barrier_depends(), but this doesn't matter.

Quoted 5 lines

Woops, h8300 doesn't have read_barrier_depends():
kernel/task_work.c:38:3: error: implicit declaration of function 'read_barrier_depends' [-Werror=implicit-function-declaration]
cc1: some warnings being treated as errors
make[2]: *** [kernel/task_work.o] Error 1

Thanks...

Quoted 5 lines

http://kisskb.ellerman.id.au/kisskb/buildresult/7238385/
Perhaps an empty definition is fine? Most architectures have:
#define read_barrier_depends() do { } while(0)

Yes. arch/h8300/include/asm/barrier.h has

	#define smp_read_barrier_depends()      read_barrier_depends()

so probably it should define read_barrier_depends() as well ?

Oleg.

Oleg Nesterov

2012-08-26 19:10 UTC #36 lore raw

PATCH 2/4 task_work: task_work_add() should not succeed after exit_task_work()

ed3e694d "move exit_task_work() past exit_files() et.al" destroyed the add/exit synchronization we had, the caller itself should ensure task_work_add() can't race with the exiting task.

However, this is not convenient/simple, and the only user which tries to do this is buggy (see the next patch). Unless the task is current, there is simply no way to do this in general.

Change exit_task_work()->task_work_run() to use the dummy "work_exited" entry to let task_work_add() know it should fail.

---
 include/linux/task_work.h |    3 +--
 kernel/task_work.c        |   22 ++++++++++++++++------
 2 files changed, 17 insertions(+), 8 deletions(-)

include/linux/task_work.h +1 -2

index fb46b03..ca5a1cf 100644
@@ -18,8 +18,7 @@ void task_work_run(void);
 
 static inline void exit_task_work(struct task_struct *task)
 {
-	if (unlikely(task->task_works))
-		task_work_run();
+	task_work_run();
 }
 
 #endif	/* _LINUX_TASK_WORK_H */

kernel/task_work.c +16 -6

index f13ec0b..65bd3c9 100644
@@ -2,16 +2,17 @@
 #include <linux/task_work.h>
 #include <linux/tracehook.h>
 
+static struct callback_head work_exited; /* all we need is ->next == NULL */
+
 int
 task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
 	struct callback_head *head;
-	/*
-	 * Not inserting the new work if the task has already passed
-	 * exit_task_work() is the responisbility of callers.
-	 */
+
 	do {
 		head = ACCESS_ONCE(task->task_works);
+		if (unlikely(head == &work_exited))
+			return -ESRCH;
 		work->next = head;
 	} while (cmpxchg(&task->task_works, head, work) != head);

@@ -30,7 +31,7 @@ task_work_cancel(struct task_struct *task, task_work_func_t func)
 	 * If cmpxchg() fails we continue without updating pprev.
 	 * Either we raced with task_work_add() which added the
 	 * new entry before this work, we will find it again. Or
-	 * we raced with task_work_run(), *pprev == NULL.
+	 * we raced with task_work_run(), *pprev == NULL/exited.
 	 */
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
 	while ((work = ACCESS_ONCE(*pprev))) {

@@ -51,7 +52,16 @@ void task_work_run(void)
 	struct callback_head *work, *head, *next;
 
 	for (;;) {
-		work = xchg(&task->task_works, NULL);
+		/*
+		 * work->func() can do task_work_add(), do not set
+		 * work_exited unless the list is empty.
+		 */
+		do {
+			work = ACCESS_ONCE(task->task_works);
+			head = !work && (task->flags & PF_EXITING) ?
+				&work_exited : NULL;
+		} while (cmpxchg(&task->task_works, work, head) != work);
+
 		if (!work)
 			break;
 		/*

Signature · 1 line

1.5.5.1

tip-bot for Oleg Nesterov

2012-09-14 06:09 UTC #37 lore raw

[tip:core/urgent] task_work: task_work_add() should not succeed after exit_task_work()

Commit-ID:  9da33de62431c7839f98156720862262272a8380
Gitweb:     http://git.kernel.org/tip/9da33de62431c7839f98156720862262272a8380
Author:     Oleg Nesterov <[email protected]>
AuthorDate: Sun, 26 Aug 2012 21:12:11 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 13 Sep 2012 16:47:34 +0200

task_work: task_work_add() should not succeed after exit_task_work()

ed3e694d "move exit_task_work() past exit_files() et.al" destroyed the add/exit synchronization we had, the caller itself should ensure task_work_add() can't race with the exiting task.

However, this is not convenient/simple, and the only user which tries to do this is buggy (see the next patch). Unless the task is current, there is simply no way to do this in general.

Change exit_task_work()->task_work_run() to use the dummy "work_exited" entry to let task_work_add() know it should fail.

Cc Al Viro <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Thomas Gleixner <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 include/linux/task_work.h |    3 +--
 kernel/task_work.c        |   22 ++++++++++++++++------
 2 files changed, 17 insertions(+), 8 deletions(-)

include/linux/task_work.h +1 -2

index fb46b03..ca5a1cf 100644
@@ -18,8 +18,7 @@ void task_work_run(void);
 
 static inline void exit_task_work(struct task_struct *task)
 {
-	if (unlikely(task->task_works))
-		task_work_run();
+	task_work_run();
 }
 
 #endif	/* _LINUX_TASK_WORK_H */

kernel/task_work.c +16 -6

index f13ec0b..65bd3c9 100644
@@ -2,16 +2,17 @@
 #include <linux/task_work.h>
 #include <linux/tracehook.h>
 
+static struct callback_head work_exited; /* all we need is ->next == NULL */
+
 int
 task_work_add(struct task_struct *task, struct callback_head *work, bool notify)
 {
 	struct callback_head *head;
-	/*
-	 * Not inserting the new work if the task has already passed
-	 * exit_task_work() is the responisbility of callers.
-	 */
+
 	do {
 		head = ACCESS_ONCE(task->task_works);
+		if (unlikely(head == &work_exited))
+			return -ESRCH;
 		work->next = head;
 	} while (cmpxchg(&task->task_works, head, work) != head);

@@ -30,7 +31,7 @@ task_work_cancel(struct task_struct *task, task_work_func_t func)
 	 * If cmpxchg() fails we continue without updating pprev.
 	 * Either we raced with task_work_add() which added the
 	 * new entry before this work, we will find it again. Or
-	 * we raced with task_work_run(), *pprev == NULL.
+	 * we raced with task_work_run(), *pprev == NULL/exited.
 	 */
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
 	while ((work = ACCESS_ONCE(*pprev))) {

@@ -51,7 +52,16 @@ void task_work_run(void)
 	struct callback_head *work, *head, *next;
 
 	for (;;) {
-		work = xchg(&task->task_works, NULL);
+		/*
+		 * work->func() can do task_work_add(), do not set
+		 * work_exited unless the list is empty.
+		 */
+		do {
+			work = ACCESS_ONCE(task->task_works);
+			head = !work && (task->flags & PF_EXITING) ?
+				&work_exited : NULL;
+		} while (cmpxchg(&task->task_works, work, head) != work);
+
 		if (!work)
 			break;
 		/*

Oleg Nesterov

2012-08-26 19:10 UTC #38 lore raw

PATCH 3/4 task_work: revert d35abdb2 "hold task_lock around checks in keyctl"

This reverts commit d35abdb28824cf74f0a106a0f9c6f3ff700a35bf.

task_lock() was added to ensure exit_mm() and thus exit_task_work() is not possible before task_work_add().

This is wrong, task_lock() must not be nested with write_lock(tasklist). And this is no longer needed, task_work_add() fails if it is called after exit_task_work().

Reported-by Dave Jones <[email protected]>

---
 security/keys/keyctl.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

security/keys/keyctl.c +0 -2

index 3364fbf..6cfc647 100644
@@ -1486,7 +1486,6 @@ long keyctl_session_to_parent(void)
 	oldwork = NULL;
 	parent = me->real_parent;
 
-	task_lock(parent);
 	/* the parent mustn't be init and mustn't be a kernel thread */
 	if (parent->pid <= 1 || !parent->mm)
 		goto unlock;

@@ -1530,7 +1529,6 @@ long keyctl_session_to_parent(void)
 	if (!ret)
 		newwork = NULL;
 unlock:
-	task_unlock(parent);
 	write_unlock_irq(&tasklist_lock);
 	rcu_read_unlock();
 	if (oldwork)

Signature · 1 line

1.5.5.1

tip-bot for Oleg Nesterov

2012-09-14 06:10 UTC #39 lore raw

[tip:core/urgent] task_work: Revert " hold task_lock around checks in keyctl"

Commit-ID:  b3f68f16dbcde6fcdf0fd27695391ff7e9d41233
Gitweb:     http://git.kernel.org/tip/b3f68f16dbcde6fcdf0fd27695391ff7e9d41233
Author:     Oleg Nesterov <[email protected]>
AuthorDate: Sun, 26 Aug 2012 21:12:14 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 13 Sep 2012 16:47:36 +0200

task_work: Revert "hold task_lock around checks in keyctl"

This reverts commit d35abdb28824cf74f0a106a0f9c6f3ff700a35bf.

task_lock() was added to ensure exit_mm() and thus exit_task_work() is not possible before task_work_add().

This is wrong, task_lock() must not be nested with write_lock(tasklist). And this is no longer needed, task_work_add() now fails if it is called after exit_task_work().

Reported-by Dave Jones <[email protected]>

Cc Al Viro <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Andrew Morton <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 security/keys/keyctl.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

security/keys/keyctl.c +0 -2

index 3364fbf..6cfc647 100644
@@ -1486,7 +1486,6 @@ long keyctl_session_to_parent(void)
 	oldwork = NULL;
 	parent = me->real_parent;
 
-	task_lock(parent);
 	/* the parent mustn't be init and mustn't be a kernel thread */
 	if (parent->pid <= 1 || !parent->mm)
 		goto unlock;

@@ -1530,7 +1529,6 @@ long keyctl_session_to_parent(void)
 	if (!ret)
 		newwork = NULL;
 unlock:
-	task_unlock(parent);
 	write_unlock_irq(&tasklist_lock);
 	rcu_read_unlock();
 	if (oldwork)

Oleg Nesterov

2012-08-26 19:10 UTC #40 lore raw

PATCH 4/4 task_work: simplify the usage in ptrace_notify() and get_signal_to_deliver()

ptrace_notify() and get_signal_to_deliver() do unnecessary things before task_work_run().

1. smp_mb__after_clear_bit() is not needed, test_and_clear_bit() implies mb().

2. And we do not need the barrier at all, in this case we only care about the "synchronous" works added by the task itself.

3. No need to clear TIF_NOTIFY_RESUME, and we should not assume task_works is the only user of this flag.

---
 kernel/signal.c |   18 ++++--------------
 1 files changed, 4 insertions(+), 14 deletions(-)

kernel/signal.c +4 ~~-14~~

index be4f856..2c681f1 100644
@@ -1971,13 +1971,8 @@ static void ptrace_do_notify(int signr, int exit_code, int why)
 void ptrace_notify(int exit_code)
 {
 	BUG_ON((exit_code & (0x7f | ~0xffff)) != SIGTRAP);
-	if (unlikely(current->task_works)) {
-		if (test_and_clear_ti_thread_flag(current_thread_info(),
-						   TIF_NOTIFY_RESUME)) {
-			smp_mb__after_clear_bit();
-			task_work_run();
-		}
-	}
+	if (unlikely(current->task_works))
+		task_work_run();
 
 	spin_lock_irq(&current->sighand->siglock);
 	ptrace_do_notify(SIGTRAP, exit_code, CLD_TRAPPED);

@@ -2198,13 +2193,8 @@ int get_signal_to_deliver(siginfo_t *info, struct k_sigaction *return_ka,
 	struct signal_struct *signal = current->signal;
 	int signr;
 
-	if (unlikely(current->task_works)) {
-		if (test_and_clear_ti_thread_flag(current_thread_info(),
-						   TIF_NOTIFY_RESUME)) {
-			smp_mb__after_clear_bit();
-			task_work_run();
-		}
-	}
+	if (unlikely(current->task_works))
+		task_work_run();
 
 	if (unlikely(uprobe_deny_signal()))
 		return 0;

Signature · 1 line

1.5.5.1

tip-bot for Oleg Nesterov

2012-09-14 06:11 UTC #41 lore raw

[tip:core/urgent] task_work: Simplify the usage in ptrace_notify() and get_signal_to_deliver()

Commit-ID:  f784e8a7989c0da3062d04bfea3db90f41e8f738
Gitweb:     http://git.kernel.org/tip/f784e8a7989c0da3062d04bfea3db90f41e8f738
Author:     Oleg Nesterov <[email protected]>
AuthorDate: Sun, 26 Aug 2012 21:12:17 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 13 Sep 2012 16:47:37 +0200

task_work: Simplify the usage in ptrace_notify() and get_signal_to_deliver()

ptrace_notify() and get_signal_to_deliver() do unnecessary things before task_work_run():

1. smp_mb__after_clear_bit() is not needed, test_and_clear_bit() implies mb().

2. And we do not need the barrier at all, in this case we only care about the "synchronous" works added by the task itself.

3. No need to clear TIF_NOTIFY_RESUME, and we should not assume task_works is the only user of this flag.

Cc Al Viro <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Thomas Gleixner <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 kernel/signal.c |   18 ++++--------------
 1 files changed, 4 insertions(+), 14 deletions(-)

kernel/signal.c +4 ~~-14~~

index be4f856..2c681f1 100644
@@ -1971,13 +1971,8 @@ static void ptrace_do_notify(int signr, int exit_code, int why)
 void ptrace_notify(int exit_code)
 {
 	BUG_ON((exit_code & (0x7f | ~0xffff)) != SIGTRAP);
-	if (unlikely(current->task_works)) {
-		if (test_and_clear_ti_thread_flag(current_thread_info(),
-						   TIF_NOTIFY_RESUME)) {
-			smp_mb__after_clear_bit();
-			task_work_run();
-		}
-	}
+	if (unlikely(current->task_works))
+		task_work_run();
 
 	spin_lock_irq(&current->sighand->siglock);
 	ptrace_do_notify(SIGTRAP, exit_code, CLD_TRAPPED);

@@ -2198,13 +2193,8 @@ int get_signal_to_deliver(siginfo_t *info, struct k_sigaction *return_ka,
 	struct signal_struct *signal = current->signal;
 	int signr;
 
-	if (unlikely(current->task_works)) {
-		if (test_and_clear_ti_thread_flag(current_thread_info(),
-						   TIF_NOTIFY_RESUME)) {
-			smp_mb__after_clear_bit();
-			task_work_run();
-		}
-	}
+	if (unlikely(current->task_works))
+		task_work_run();
 
 	if (unlikely(uprobe_deny_signal()))
 		return 0;

Oleg Nesterov

2012-09-06 17:58 UTC #42 lore raw

Re: [PATCH 0/4] (Was: lockdep trace from posix timers)

Ping...

Al, will you agree with these changes?

Peter, do you think you can do your make-it-lockless patch (hehe, I think this is not possible ;) on top?

Quoted 115 lines · Oleg Nesterov

Quoted 3 lines · Oleg Nesterov

Peter, if you think it can work for you and if you agree with the implementation I will be happy to send the patch.

I think I should try anyway ;)

To simplify the review, I attached the resulting code below.

Changes:

- Comments.

- Not sure this is really better, but task_work_run() does not need to actually take pi_lock, unlock_wait is enough.

However, in this case the dummy entry is better than the fake pointer.

Oleg.

#include <linux/spinlock.h>
#include <linux/task_work.h>
#include <linux/tracehook.h>

static struct callback_head work_exited; /* all we need is ->next == NULL */

int
task_work_add(struct task_struct *task, struct callback_head *work, bool notify)

{
	struct callback_head *head;

	do {
		head = ACCESS_ONCE(task->task_works);
		if (unlikely(head == &work_exited))
			return -ESRCH;
		work->next = head;
	} while (cmpxchg(&task->task_works, head, work) != head);

	if (notify)
		set_notify_resume(task);
	return 0;
}

struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func)

{
	struct callback_head **pprev = &task->task_works;
	struct callback_head *work = NULL;
	unsigned long flags;
	/*
	 * If cmpxchg() fails we continue without updating pprev.
	 * Either we raced with task_work_add() which added the
	 * new entry before this work, we will find it again. Or
	 * we raced with task_work_run(), *pprev == NULL/exited.
	 */
	raw_spin_lock_irqsave(&task->pi_lock, flags);
	while ((work = ACCESS_ONCE(*pprev))) {
		read_barrier_depends();
		if (work->func != func)
			pprev = &work->next;
		else if (cmpxchg(pprev, work, work->next) == work)
			break;
	}
	raw_spin_unlock_irqrestore(&task->pi_lock, flags);

	return work;
}

void task_work_run(void)

{
	struct task_struct *task = current;
	struct callback_head *work, *head, *next;

	for (;;) {
		/*
		 * work->func() can do task_work_add(), do not set
		 * work_exited unless the list is empty.
		 */
		do {
			work = ACCESS_ONCE(task->task_works);
			head = !work && (task->flags & PF_EXITING) ?
				&work_exited : NULL;
		} while (cmpxchg(&task->task_works, work, head) != work);

		if (!work)
			break;
		/*
		 * Synchronize with task_work_cancel(). It can't remove
		 * the first entry == work, cmpxchg(task_works) should
		 * fail, but it can play with *work and other entries.
		 */
		raw_spin_unlock_wait(&task->pi_lock);
		smp_mb();

		/* Reverse the list to run the works in fifo order */
		head = NULL;
		do {
			next = work->next;
			work->next = head;
			head = work;
			work = next;
		} while (work);

		work = head;
		do {
			next = work->next;
			work->func(work);
			work = next;
			cond_resched();
		} while (work);
	}
}

Peter Zijlstra

2012-09-06 18:35 UTC #43 lore raw

Re: [PATCH 0/4] (Was: lockdep trace from posix timers)

Quoted 1 line · Oleg Nesterov

Ping...

Right, email backlog :-)

Quoted 2 lines

Peter, do you think you can do your make-it-lockless patch (hehe, I think this is not possible ;) on top?

Sure, I was trying to see if I could play games with the _cancel semantics that would satisfy the two callsites and be possible. No joy yet though.

Anyway, do you want me to take these patches through -tip?

Oleg Nesterov

2012-09-07 13:11 UTC #44 lore raw

Re: [PATCH 0/4] (Was: lockdep trace from posix timers)

Quoted 2 lines · Peter Zijlstra

Anyway, do you want me to take these patches through -tip?

This would be great, thanks.

Oleg.

Peter Zijlstra

2012-08-28 16:29 UTC #45 lore raw

Quoted 3 lines · Oleg Nesterov

Peter, if you think it can work for you and if you agree with the implementation I will be happy to send the patch.

Yeah I think it would work, but I'm not sure why you're introducing the cmp_xchg helper just for this..

Anyway, how about something like the below, it pops the works one by one when running, that way when the cancel will only return NULL when the work is either being executed or already executed.

( And yeah, I know, its not FIFO ;-)

---
 include/linux/task_work.h |    7 +--
 kernel/exit.c             |    2 +-
 kernel/task_work.c        |  130 +++++++++++++++++++++++++--------------------
 3 files changed, 75 insertions(+), 64 deletions(-)

include/linux/task_work.h +1 -6

index fb46b03..f365416 100644
@@ -15,11 +15,6 @@ init_task_work(struct callback_head *twork, task_work_func_t func)
 int task_work_add(struct task_struct *task, struct callback_head *twork, bool);
 struct callback_head *task_work_cancel(struct task_struct *, task_work_func_t);
 void task_work_run(void);
-
-static inline void exit_task_work(struct task_struct *task)
-{
-	if (unlikely(task->task_works))
-		task_work_run();
-}
+void task_work_exit(void);
 
 #endif	/* _LINUX_TASK_WORK_H */

kernel/exit.c +1 -1

index f65345f..92aa94b 100644
@@ -992,7 +992,7 @@ void do_exit(long code)
 	exit_shm(tsk);
 	exit_files(tsk);
 	exit_fs(tsk);
-	exit_task_work(tsk);
+	task_work_exit();
 	check_stack_usage();
 	exit_thread();

kernel/task_work.c +73 ~~-57~~

152 lines not on this page · raw message

Oleg Nesterov

2012-08-28 16:59 UTC #46 lore raw

Quoted 8 lines · Peter Zijlstra

Quoted 3 lines · Oleg Nesterov
Peter, if you think it can work for you and if you agree with the implementation I will be happy to send the patch.
Yeah I think it would work, but I'm not sure why you're introducing the cmp_xchg helper just for this..

Please look at 1-4 the patches I sent (only 1-2 are relevant), I removed this helper. Although I still think it makes sense, but of course not in task_work.c.

Quoted 19 lines

struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func) {

kernel/task_work.c +0 ~~-16~~

-	unsigned long flags;
-	struct callback_head *last, *res = NULL;
-
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	last = task->task_works;
-	if (last) {
-		struct callback_head *q = last, *p = q->next;
-		while (1) {
-			if (p->func == func) {
-				q->next = p->next;
-				if (p == last)
-					task->task_works = q == p ? NULL : q;
-				res = p;
-				break;
-			}
-			if (p == last)

kernel/task_work.c line 48

Quoted 10 lines

kernel/task_work.c +7 -3

-				break;
-			q = p;
-			p = q->next;
+	struct callback_head **workp, *work;
+
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {

But you can't dereference this pointer. Without some locking this can race with another task_work_cancel() or task_work_run(), this work can be free/unmapped/reused.

kernel/task_work.c line 50

Quoted 2 lines

kernel/task_work.c +2 -0

+			if (cmpxchg(workp, work, work->next) == work)
+				return work;

Or this can race with task_work_cancel(work) + task_work_add(work). cmpxchg() can succeed even if work->func is already different.

Quoted 21 lines

kernel/task_work.c +1 ~~-19~~

+static callback_head *task_work_pop(void)
 {
-	struct task_struct *task = current;
-	struct callback_head *p, *q;
-
-	while (1) {
-		raw_spin_lock_irq(&task->pi_lock);
-		p = task->task_works;
-		task->task_works = NULL;
-		raw_spin_unlock_irq(&task->pi_lock);
-
-		if (unlikely(!p))
-			return;
-
-		q = p->next; /* head */
-		p->next = NULL; /* cut it */
-		while (q) {
-			p = q->next;
-			q->func(q);
-			q = p;
-		}

kernel/task_work.c line 72

Quoted 10 lines

kernel/task_work.c +10 -0

+	struct callback_head **head = &current->task_work;
+	struct callback_head *entry, *old_entry;
+
+	entry = *head;
+	for (;;) {
+		if (!entry || entry == &dead)
+			return NULL;
+
+		old_entry = entry;
+		entry = cmpxchg(head, entry, entry->next);

Well, this obviously means cmpxchg() for each entry...

Quoted 1 line

( And yeah, I know, its not FIFO ;-)

Cough. akpm didn't like fifo, Linus disliked it too...

And now you! Whats going on??? ;)

Oleg.

Oleg Nesterov

2012-08-28 17:10 UTC #47 lore raw

Quoted 13 lines · Oleg Nesterov

kernel/task_work.c line 48
Quoted 6 lines · Peter Zijlstra
kernel/task_work.c +5 -0
+again:
+	workp = &task->task_works;
+	work = *workp;
+	while (work) {
+		if (work->func == func) {
But you can't dereference this pointer. Without some locking this can race with another task_work_cancel() or task_work_run(), this work can be free/unmapped/reused.

Quoted 5 lines

kernel/task_work.c line 50
Quoted 2 lines
kernel/task_work.c +2 -0
+			if (cmpxchg(workp, work, work->next) == work)
+				return work;
Or this can race with task_work_cancel(work) + task_work_add(work). cmpxchg() can succeed even if work->func is already different.

Even simpler, this can race with another task_work_cancel() which is going to remove work->next.

Oleg.

Peter Zijlstra

2012-08-28 17:29 UTC #48 lore raw

Quoted 15 lines · Oleg Nesterov

kernel/task_work.c line 48
Quoted 10 lines
struct callback_head *
task_work_cancel(struct task_struct *task, task_work_func_t func) {
kernel/task_work.c +7 -0
+     struct callback_head **workp, *work;
+
+again:
+     workp = &task->task_works;
+     work = *workp;
+     while (work) {
+             if (work->func == func) {
But you can't dereference this pointer. Without some locking this can race with another task_work_cancel() or task_work_run(), this work can be free/unmapped/reused.

Quoted 5 lines

kernel/task_work.c line 50
Quoted 2 lines
kernel/task_work.c +2 -0
+                     if (cmpxchg(workp, work, work->next) == work)
+                             return work;
Or this can race with task_work_cancel(work) + task_work_add(work). cmpxchg() can succeed even if work->func is already different.

Bah.. you and your races ;-)

Surely we can do this locklessly.. I'll go try harder still.

Oleg Nesterov

2012-08-29 15:23 UTC #49 lore raw

Quoted 2 lines · Peter Zijlstra

Surely we can do this locklessly.. I'll go try harder still.

I doubt...

Even ignore work->func check, somehow you need to ensure that work->next == new can't be changed durung cmpxchg(..., new).

Anyway, if this is possible, can't you do this on top of 1-4 I sent? There are simple, and solve the problems we discusssed.

Off-topic. This is really minor, bur can't we simplify llist_add()?

	static inline bool llist_add(struct llist_node *new, struct llist_head *head)
	{
		struct llist_node *old;

		do {
			old = ACCESS_ONCE(head->first);
			new->next = old;
		} while (cmpxchg(&head->first, old, new) != old);

		return old == NULL;
	}

looks simpler and saves a couple of insns. The likely case should assume that cmpxchg() succeeds after the 1st attempt. If it fails, another LOAD from head->first should be very cheap.

And note this ACCESS_ONCE(head->first) above. I think that (in theory) the current code needs it too. But only in theory, I guess.

Oleg.

Oleg Nesterov

2012-08-20 14:59 UTC #50 lore raw

Quoted 7 lines · Peter Zijlstra

Quoted 2 lines · Oleg Nesterov
I still think that task_work_add() should synhronize with exit_task_work() itself and fail if necessary. But I wasn't able to convince Al ;)
I'm not at all sure how that relates to needing task_lock() in the keyctl stuff.

To serialize with exit_mm() which clears ->mm.

We shouldn't do task_work_add(task) if the exiting task has already passed exit_task_work(). There is no way to do this after ed3e694d7 (and I think this is wrong), so keyctl relies on the fact that exit_task_work() is called after exit_mm().

Quoted 2 lines

Also, can't task_work use llist stuff? That would also avoid using ->pi_lock.

Not sure.... task_work_add/run can use cmpxchg, but _cancel can't.

Oleg.

Oleg Nesterov

2012-08-20 15:47 UTC #51 lore raw