ipc/msg.c "cleanup" breaks fakeroot on Alpha
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
@@ -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
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
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
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
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
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_receiverstructure. The structure is stored on the stack ofmsr->r_tsk.
Thesmp_mb()guarantees that thewake_up_processis complete beforeERR_PTR(res)is stored intomsr->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 bymsg_lock(msqid), which is a spinlock. One spinlock for each queue.
- if a receiving thread doesn't find a message, then it adds amsg_receiverstructure intomsq->q_receivers. This linked list is stored in the message queue structure and protected bymsg_lock(msqid).
- if a sending thread finds amsg_receiverstructure, then it removes the structure from themsq->q_receiverslinked list, places the message intomsr->r_msgand wakes up the receiver. All operations happen undermsg_lock(msqid)
- the receiver notices that there is a message in it'smsr->r_msgstructure and copies it to user space, without acquiringmsg_lock(msqid).
ipc/sem.cuses the same idea, I added a longer block with documentation (around line 150 inipc/sem.c)I'm only aware of one tricky race:
- the sender callswake_up_process().
- as soon as the receiver finds something inr_msg, it can return to user space. user space can call exit(3).do_exitdestroys the task structure.
-wake_up_processwill cause an oops if it's called afterdo_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_msgisERR_PTR(-EAGAIN). The sender first sets it to NULL ("message pending"), then callswake_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_relaxis abarrier().
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 byexpunge_all. I.e.:
- either themsq->q_receiverslinked list got corrupted
- or the target thread was destroyed beforewake_up_processcompleted. Theoretically, both things are impossible:
-msq->q_receiversis protected bymsq_lock()
- the target threadtask_structis 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
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 insys_semtimedop().
What do you mean with remap?
Quoted 14 lines
So, what am I missing here? How does a
msgrcv()racing with anrmid()avoid taking a lock on a message queue that just got freed? (Theipc_lock_by_ptr()in "Lockless receive, part 3".) My concern is the following sequence of steps:o
expunge_all()invokeswake_up_process()and setsr_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 tofreeque(), which runs through the
rest of its processing, finally callingipc_rcu_putref().
Quoted 11 lines
o
ipc_rcu_putref()invokescall_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 anrcu_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
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 insys_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 anrmid()avoid taking a lock on a message queue that just got freed? (Theipc_lock_by_ptr()in "Lockless receive, part 3".) My concern is the following sequence of steps:o
expunge_all()invokeswake_up_process()and setsr_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 tofreeque(), which runs through the
rest of its processing, finally callingipc_rcu_putref().Quoted 9 lines
o
ipc_rcu_putref()invokescall_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 anrcu_read_lock() -- but too late!!!
Quoted 9 lines
Not too late:
sys_msgrcv()checks msr_d.r_msr, notices that the value is-EIDRMand returns to user space with-EIDRMimmediately. 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 thercu_read_lock()guarantees there is no rcu grace period between the test for-EAGAINand theipc_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 inexpunge_all, called fromsys_msgctl. Thus it must be anmsgctl(IPC_SET).IPC_SETis special: it callsexpunge_all(-EAGAIN): that's necessary becauseIPC_SETcan change the permissions. Unfortunately, faked doesn't useIPC_SETat all :-(Falk - could you strace your "fakeroot ls" test? Are there any
IPC_SETcalls?
Which gcc version do you use? Is it possible that gcc auto-inlined something?--
Manfred