Skip to contentSkip to conversation

ipc/msg.c "cleanup" breaks fakeroot on Alpha

PATCH Falk Hueffner 5 participants 8 messages Nov 4, 2006 – Nov 6, 2006 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

Hi,

this hunk

commit 5a06a363ef48444186f18095ae1b932dddbbfa89

Author: Ingo Molnar <[email protected]>
Date:   Sun Jul 30 03:04:11 2006 -0700

[PATCH] ipc/msg.c: clean up coding style

Clean up ipc/msg.c to conform to Documentation/CodingStyle. (before it was an inconsistent hodepodge of various coding styles)

Verified that the before/after .o's are identical.

ipc/msg.c +1 -1
index cd92d34..2b4fccf 100644
@@ -47,12 +47,12 @@
 struct msg_receiver {
 	struct list_head	r_list;
 	struct task_struct	*r_tsk;
 
 	int			r_mode;
 	long			r_msgtype;
 	long			r_maxsize;
 
-	struct msg_msg* volatile r_msg;
+	volatile struct msg_msg	*r_msg;
 };
 

breaks fakeroot on Alpha (variously hangs or oopses). Backing it out of 2.6.19-rc4 fixes the issue. Is it possible that this change (which clearly does change semantics) was made in error?

Signature · 1 line
	Falk
#1 lore raw
Quoted 7 lines · Falk Hueffner
ipc/msg.c +1 -1
-	struct msg_msg* volatile r_msg;
+	volatile struct msg_msg	*r_msg;
 };

breaks fakeroot on Alpha (variously hangs or oopses). Backing it out of 2.6.19-rc4 fixes the issue. Is it possible that this change (which clearly does change semantics) was made in error?

correct, it was an error, lets back it out.

Another interesting question is: what in the IPC code relies on the volatility of this field, and shouldnt it be converted to explicit barriers instead?

Ingo

#2 lore raw
Quoted 13 lines · Ingo Molnar
Quoted 7 lines · Falk Hueffner
ipc/msg.c +1 -1
-	struct msg_msg* volatile r_msg;
+	volatile struct msg_msg	*r_msg;
 };

breaks fakeroot on Alpha (variously hangs or oopses). Backing it out of 2.6.19-rc4 fixes the issue. Is it possible that this change (which clearly does change semantics) was made in error?

correct, it was an error, lets back it out.

Quoted 3 lines

Another interesting question is: what in the IPC code relies on the volatility of this field, and shouldnt it be converted to explicit barriers instead?

Absolutely. Anything that depends on "volatile" is broken by definition, since volatile does _not_ imply memory barriers, and while it may constrict the compiler in certain ways (and thus effectively make it work on things like x86 where the memory ordering is fairly easy to get to work), it is not going to do _anything_ on some other architectures, except just perhaps make a bug harder to trigger.

Falk - do you have a couple of the oopses (the more, the better: race conditions tend to have subtle oopses, and with more oopses it is easier to try to figure out the pattern) that you can point people at, so that we can get an idea of what's going on.

This looks like a classic case of "volatile is a sign of a bug".

Linus

#3 lore raw
Quoted 4 lines · Linus Torvalds

Falk - do you have a couple of the oopses (the more, the better: race conditions tend to have subtle oopses, and with more oopses it is easier to try to figure out the pattern) that you can point people at, so that we can get an idea of what's going on.

I've got only one, it's perfectly reproducible with e.g. "fakeroot ls":

ksymoops 2.4.11 on alpha 2.6.19-rc4. Options used
-V (default)
-k /proc/ksyms (default)
-l /proc/modules (default)
-o /lib/modules/2.6.19-rc4/ (default) -m /src/linux-2.6.19-rc4/System.map (specified)

Error (regular_file): read_ksyms stat /proc/ksyms failed No modules in ksyms, skipping objects
No ksyms, skipping lsmod

Nov  4 19:00:23 juist kernel: Unable to handle kernel paging request at virtual address 0000025800000683
Nov  4 19:00:23 juist kernel: faked-sysv(2111): Oops 0
Nov  4 19:00:23 juist kernel: pc = [<fffffc0000322810>]  ra = [<fffffc0000322810>]  ps = 0007    Not tainted
Using defaults from ksymoops -t elf64-alpha -a alpha
Nov  4 19:00:23 juist kernel: v0 = fffffc0000724c00  t0 = 0000000000000000  t1 = 0000000000000001
Nov  4 19:00:23 juist kernel: t2 = 00000000000003e8  t3 = fffffffffffffff5  t4 = fffffc006f36bde8
Nov  4 19:00:23 juist kernel: t5 = fffffc006f36bde8  t6 = 00000200001c41cc  t7 = fffffc006f368000
Nov  4 19:00:23 juist kernel: s0 = 000000000000000f  s1 = 0000025800000683  s2 = fffffc006fdf3e10
Nov  4 19:00:23 juist kernel: s3 = 0000000000000000  s4 = fffffc00006ca8e0  s5 = 0000000000000100
Nov  4 19:00:23 juist kernel: s6 = fffffc006f36bd78
Nov  4 19:00:23 juist kernel: a0 = 0000000000000007  a1 = fffffc006f36bda8  a2 = 0000000000000000
Nov  4 19:00:23 juist kernel: a3 = 0000000000000001  a4 = 0000000000000000  a5 = 000002000000cf80
Nov  4 19:00:23 juist kernel: t8 = 00000200001c41bc  t9 = 00000200001c41bc  t10= 000000007fffffff
Nov  4 19:00:23 juist kernel: t11= 00000200001c54d2  pv = fffffc00003229b0  at = 000000000749d915
Nov  4 19:00:23 juist kernel: gp = fffffc0000720200  sp = fffffc006f36bd78
Nov  4 19:00:23 juist kernel: Trace:
Nov  4 19:00:23 juist kernel: [<fffffc00003f8228>] expunge_all+0x58/0x90
Nov  4 19:00:23 juist kernel: [<fffffc00003f884c>] sys_msgctl+0x1cc/0x730
Nov  4 19:00:23 juist kernel: [<fffffc00003112a4>] entSys+0xa4/0xc0
Nov  4 19:00:23 juist kernel: Code: 47f0040a  b59e0020  b75e0000  47f2040c  4921f629  d35fff0a <a44a0000> 47e0040b 
Quoted 3 lines
Quoted 3 lines

RA; fffffc0000322810 <try_to_wake_up+40/180>

PC; fffffc0000322810 <try_to_wake_up+40/180> <=====

Trace; fffffc00003f8228 <expunge_all+58/90>
Trace; fffffc00003f884c <sys_msgctl+1cc/730>
Trace; fffffc00003112a4 <entSys+a4/c0>

Code; fffffc00003227f8 <try_to_wake_up+28/180>
0000000000000000 <_PC>:
Code; fffffc00003227f8 <try_to_wake_up+28/180>
0: 0a 04 f0 47 mov a0,s1
Code; fffffc00003227fc <try_to_wake_up+2c/180>
4: 20 00 9e b5 stq s3,32(sp)
Code; fffffc0000322800 <try_to_wake_up+30/180>
8: 00 00 5e b7 stq ra,0(sp)
Code; fffffc0000322804 <try_to_wake_up+34/180>
c: 0c 04 f2 47 mov a2,s3
Code; fffffc0000322808 <try_to_wake_up+38/180>
10: 29 f6 21 49 zapnot s0,0xf,s0
Code; fffffc000032280c <try_to_wake_up+3c/180>
14: 0a ff 5f d3 bsr ra,fffffffffffffc40 <_PC+0xfffffffffffffc40>
Code; fffffc0000322810 <try_to_wake_up+40/180> <=====
18: 00 00 4a a4 ldq t1,0(s1) <=====
Code; fffffc0000322814 <try_to_wake_up+44/180>
1c: 0b 04 e0 47 mov v0,s2

1 error issued. Results may not be reliable.

Signature · 1 line
	Falk

A message that is not in the archive (sent off-list or not yet received): [email protected]

#5 lore raw
Quoted 3 lines · Linus Torvalds

[ Removed the kernel mailing list ]

[kernel mailing list added back]

Quoted 13 lines

As far as I can tell, people hold one or the other, but not both, and happily do strange things to "r_msg". The code seems to _know_ that it is racy, since in addition to the volatile, it does things like:

		...
               msr->r_msg = NULL;
               wake_up_process(msr->r_tsk);
               smp_mb();
               msr->r_msg = ERR_PTR(res);
		...

and that memory barrier again doesn't really seem to make a whole lot of sense.

msr is a msg_receiver structure. The structure is stored on the stack of msr->r_tsk.
The smp_mb() guarantees that the wake_up_process is complete before ERR_PTR(res) is stored into msr->r_msg.

Quoted 4 lines

But I don't know. It clearly _tries_ to do some smart locking, I just don't see what the rules are.

The codes tries to to a lockless receive:
- the mutex is only required to create/destroy queues.
- normal queue operations are protected by msg_lock(msqid), which is a spinlock. One spinlock for each queue.
- if a receiving thread doesn't find a message, then it adds a msg_receiver structure into msq->q_receivers. This linked list is stored in the message queue structure and protected by msg_lock(msqid).
- if a sending thread finds a msg_receiver structure, then it removes the structure from the msq->q_receivers linked list, places the message into msr->r_msg and wakes up the receiver. All operations happen under msg_lock(msqid)
- the receiver notices that there is a message in it's msr->r_msg structure and copies it to user space, without acquiring msg_lock(msqid).

ipc/sem.c uses the same idea, I added a longer block with documentation (around line 150 in ipc/sem.c)

I'm only aware of one tricky race:
- the sender calls wake_up_process().
- as soon as the receiver finds something in r_msg, it can return to user space. user space can call exit(3). do_exit destroys the task structure.
- wake_up_process will cause an oops if it's called after do_exit().
This race happened on s390. The solution is this block:

               msr->r_msg = NULL;
               wake_up_process(msr->r_tsk);
               smp_mb();
               msr->r_msg = ERR_PTR(res);

Initially, r_msg is ERR_PTR(-EAGAIN). The sender first sets it to NULL ("message pending"), then calls wake_up_process(), then a memory barrier, then the final value.

Back to the bug report:
"volatile" shouln't be necessary. The critical part is this loop:

               msg = (struct msg_msg*)msr_d.r_msg;
               while (msg == NULL) {
                       cpu_relax();
                       msg = (struct msg_msg *)msr_d.r_msg;
               }

And cpu_relax is a barrier().
On i386, removing the "volatile" has no effect, the .o remains identical. Falk, could you compare the .o files with/without volatile? Are there any differences?

The oops was caused by try_to_wake_up, called by expunge_all.
I.e.:
- either the msq->q_receivers linked list got corrupted
- or the target thread was destroyed before wake_up_process completed. Theoretically, both things are impossible:
- msq->q_receivers is protected by msq_lock()
- the target thread task_struct is guaranteed to remain in scope due to the "msg == NULL" loop.

I'll try to reproduce the oops on i386 - but I don't see a bug right now.

--
Manfred

#6 lore raw
Quoted 18 lines · Manfred Spraul
Quoted 3 lines · Linus Torvalds

[ Removed the kernel mailing list ]

[kernel mailing list added back]

Quoted 11 lines

As far as I can tell, people hold one or the other, but not both, and happily do strange things to "r_msg". The code seems to _know_ that it is racy, since in addition to the volatile, it does things like:

		...
              msr->r_msg = NULL;
              wake_up_process(msr->r_tsk);
              smp_mb();
              msr->r_msg = ERR_PTR(res);
		...
Quoted 7 lines
Quoted 3 lines

and that memory barrier again doesn't really seem to make a whole lot of sense.

msr is a msg_receiver structure. The structure is stored on the stack of msr->r_tsk.
The smp_mb() guarantees that the wake_up_process is complete before ERR_PTR(res) is stored into msr->r_msg.

OK, so matching code in sys_msgrcv() spins on the r_tsk pointer until it becomes non-NULL. Can't say that I understand why the first assignment to msr->r_msg cannot simply be ERR_PTR(res), but I am probably missing something basic. But your explanation below clears that up, thank you!

I also don't understand why the code in sys_msgrcv() doesn't have to remap the msqid, similar to the way it is done in sys_semtimedop().

Is there some reference counter that I am failing to see? There is the ipc_rcu_getref() on the send side, and something similar seems like it would work on the read side -- though with additional cache thrashing, so probably cheaper to remap the id.

So, what am I missing here? How does a msgrcv() racing with an rmid() avoid taking a lock on a message queue that just got freed? (The ipc_lock_by_ptr() in "Lockless receive, part 3".) My concern is the following sequence of steps:

o expunge_all() invokes wake_up_process() and sets r_msg.

o sys_msgrcv() is awakened, but for whatever reason does
not actually start executing (e.g., lots of other busy processes at higher priority).

o expunge_all() returns to freeque(), which runs through the
rest of its processing, finally calling ipc_rcu_putref().

o ipc_rcu_putref() invokes call_rcu() to free the message
queue after a grace period.

o ipc_immediate_free() is invoked at the end of a grace
period, freeing the message queue.

o sys_msgrcv() finally gets a chance to run, and does an

	rcu_read_lock() -- but too late!!!

o sys_msgrcv() does ipc_lock_by_ptr() on a message-queue
data structure that has already been freed. Things degrade rapidly from here...

Or is there some subtlety that prevents this?

If this problem is real, either an ipc_rcu_getref() before the msg_unlock() before the schedule() and an ipc_rcu_putref() after the rcu_read_lock() following the schedule(), both in sys_msgrcv() on the one hand... Or remap the msqid after the rcu_read_lock() following the schedule on the other.

Thanx, Paul

Quoted 65 lines
Quoted 5 lines

But I don't know. It clearly _tries_ to do some smart locking, I just don't see what the rules are.

The codes tries to to a lockless receive:
- the mutex is only required to create/destroy queues.
- normal queue operations are protected by msg_lock(msqid), which is a spinlock. One spinlock for each queue.
- if a receiving thread doesn't find a message, then it adds a msg_receiver structure into msq->q_receivers. This linked list is stored in the message queue structure and protected by msg_lock(msqid).
- if a sending thread finds a msg_receiver structure, then it removes the structure from the msq->q_receivers linked list, places the message into msr->r_msg and wakes up the receiver. All operations happen under msg_lock(msqid)
- the receiver notices that there is a message in it's msr->r_msg structure and copies it to user space, without acquiring msg_lock(msqid).

ipc/sem.c uses the same idea, I added a longer block with documentation (around line 150 in ipc/sem.c)

I'm only aware of one tricky race:
- the sender calls wake_up_process().
- as soon as the receiver finds something in r_msg, it can return to user space. user space can call exit(3). do_exit destroys the task structure.
- wake_up_process will cause an oops if it's called after do_exit(). This race happened on s390. The solution is this block:

               msr->r_msg = NULL;
               wake_up_process(msr->r_tsk);
               smp_mb();
               msr->r_msg = ERR_PTR(res);

Initially, r_msg is ERR_PTR(-EAGAIN). The sender first sets it to NULL ("message pending"), then calls wake_up_process(), then a memory barrier, then the final value.

Back to the bug report:
"volatile" shouln't be necessary. The critical part is this loop:

               msg = (struct msg_msg*)msr_d.r_msg;
               while (msg == NULL) {
                       cpu_relax();
                       msg = (struct msg_msg *)msr_d.r_msg;
               }

And cpu_relax is a barrier().
On i386, removing the "volatile" has no effect, the .o remains identical. Falk, could you compare the .o files with/without volatile? Are there any differences?

The oops was caused by try_to_wake_up, called by expunge_all. I.e.:
- either the msq->q_receivers linked list got corrupted
- or the target thread was destroyed before wake_up_process completed. Theoretically, both things are impossible:
- msq->q_receivers is protected by msq_lock()
- the target thread task_struct is guaranteed to remain in scope due to the "msg == NULL" loop.

I'll try to reproduce the oops on i386 - but I don't see a bug right now.

--
Manfred

#7 lore raw
Quoted 5 lines · Paul E. McKenney

I also don't understand why the code in sys_msgrcv() doesn't have to remap the msqid, similar to the way it is done in sys_semtimedop().

What do you mean with remap?

Quoted 14 lines

So, what am I missing here? How does a msgrcv() racing with an rmid() avoid taking a lock on a message queue that just got freed? (The ipc_lock_by_ptr() in "Lockless receive, part 3".) My concern is the following sequence of steps:

o expunge_all() invokes wake_up_process() and sets r_msg.

o sys_msgrcv() is awakened, but for whatever reason does
not actually start executing (e.g., lots of other busy processes at higher priority).

o expunge_all() returns to freeque(), which runs through the
rest of its processing, finally calling ipc_rcu_putref().

Quoted 11 lines

o ipc_rcu_putref() invokes call_rcu() to free the message
queue after a grace period.

o ipc_immediate_free() is invoked at the end of a grace
period, freeing the message queue.

o sys_msgrcv() finally gets a chance to run, and does an

	rcu_read_lock() -- but too late!!!

Not too late:
sys_msgrcv() checks msr_d.r_msr, notices that the value is -EIDRM and returns to user space with -EIDRM immediately. This codepath doesn't touch the message queue pointer, thus it doesn't matter that the message queue is already freed.
The code only touches the message queue pointer if msr_d.r_msr is -EAGAIN - and the rcu_read_lock() guarantees there is no rcu grace period between the test for -EAGAIN and the ipc_lock_by_ptr. Thus this should be safe.

But back to the oops:
The oops happens in expunge_all, called from sys_msgctl. Thus it must be an msgctl(IPC_SET).
IPC_SET is special: it calls expunge_all(-EAGAIN): that's necessary because IPC_SET can change the permissions. Unfortunately, faked doesn't use IPC_SET at all :-(

Falk - could you strace your "fakeroot ls" test? Are there any IPC_SET calls? Which gcc version do you use? Is it possible that gcc auto-inlined something?

--
Manfred

#8 lore raw
Quoted 6 lines · Manfred Spraul
Quoted 3 lines · Paul E. McKenney

I also don't understand why the code in sys_msgrcv() doesn't have to remap the msqid, similar to the way it is done in sys_semtimedop().

What do you mean with remap?

What ipc_lock() does, more or less.

Quoted 23 lines
Quoted 14 lines

So, what am I missing here? How does a msgrcv() racing with an rmid() avoid taking a lock on a message queue that just got freed? (The ipc_lock_by_ptr() in "Lockless receive, part 3".) My concern is the following sequence of steps:

o expunge_all() invokes wake_up_process() and sets r_msg.

o sys_msgrcv() is awakened, but for whatever reason does
not actually start executing (e.g., lots of other busy processes at higher priority).

o expunge_all() returns to freeque(), which runs through the
rest of its processing, finally calling ipc_rcu_putref().

Quoted 9 lines

o ipc_rcu_putref() invokes call_rcu() to free the message
queue after a grace period.

o ipc_immediate_free() is invoked at the end of a grace
period, freeing the message queue.

o sys_msgrcv() finally gets a chance to run, and does an

	rcu_read_lock() -- but too late!!!
Quoted 9 lines

Not too late:
sys_msgrcv() checks msr_d.r_msr, notices that the value is -EIDRM and returns to user space with -EIDRM immediately. This codepath doesn't touch the message queue pointer, thus it doesn't matter that the message queue is already freed.
The code only touches the message queue pointer if msr_d.r_msr is -EAGAIN - and the rcu_read_lock() guarantees there is no rcu grace period between the test for -EAGAIN and the ipc_lock_by_ptr. Thus this should be safe.

OK, seems like it does handle that scenario. Sorry for the noise!

And the other possible scenario, where the wakeup happens before the assignment of NULL to msr_d.r_msr, be prevented by the two rounds of rq lock (one in try_to_wake_up(), the other when the task actually starts running).

Thanx, Paul

Quoted 14 lines

But back to the oops:
The oops happens in expunge_all, called from sys_msgctl. Thus it must be an msgctl(IPC_SET).
IPC_SET is special: it calls expunge_all(-EAGAIN): that's necessary because IPC_SET can change the permissions. Unfortunately, faked doesn't use IPC_SET at all :-(

Falk - could you strace your "fakeroot ls" test? Are there any IPC_SET calls?
Which gcc version do you use? Is it possible that gcc auto-inlined something?

--
Manfred