recursive spinlocks. Shoot.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 9 lines · In article <[email protected]> you wrote:
Quoted 7 lines
Quoted 4 lines
#define nestlock_lock(snl) \ do { \ if ((snl)->uniq == current) { \That would be able to read uniq while it is being written by something else (which it can, according to the code below). It needs protection.
No it does not, look better.
I'm afraid I only see that it does!
Quoted 11 lines
Quoted 8 lines
Quoted 5 lines
atomic_inc(&(snl)->count); \ } else { \ spin_lock(&(snl)->lock); \ atomic_inc(&(snl)->count); \ (snl)->uniq = current; \Hmm .. else we wait for the lock, and then set count and uniq, while somebody else may have entered and be reading it :-). You exit with
Nope, think about a case were it breaks. False negatives are not possible because it is set by the same task and false positives either.
No. This is not true. Imagine two threads, timed as follows ...
.
.
.
.if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .
(snl)->uniq = current; <-> if ((snl)->uniq == current) {
atomic_inc(&(snl)->count);
} else {
spin_lock(&(snl)->lock);
atomic_inc(&(snl)->count);
(snl)->uniq = current; There you are. One hits the read exactly at the time the other does a write. Bang.
Quoted 8 lines
Quoted 3 lines
Well, it's not assembler either, but at least it's easily comparable with the nonrecursive version. It's essentially got an extra if and an inc in the lock. That's all.
Well, there's a little difference. In case of contention, you loop with your custom try lock while I used the optimized asm code inside
spin_lock. But again, I believe we didn't lose anything with the removal of this code (nested/recursive locks) from the kernel.
We lose hours of programmers time, looking for deadlocks caused by accidently taking the same spinlock twice and not knowing it.
A question in my mind is whether a fault in a third thread, like sleeping with a spinlock held, can make a recursive spinlock into a fault causer ... no, I don't see any way.
Peter
Quoted 19 lines · Peter T. Breuer
No. This is not true. Imagine two threads, timed as follows ...
. . . .if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .(snl)->uniq = current; <-> if ((snl)->uniq == current) { atomic_inc(&(snl)->count); } else { spin_lock(&(snl)->lock); atomic_inc(&(snl)->count); (snl)->uniq = current;
Quoted 2 lines
There you are. One hits the read exactly at the time the other does a write. Bang.
So, what's bang for you ? The second task (the one that reads "uniq") will either see "uniq" as NULL or as (task1)->current. And it'll go acquiring the lock, as expected. Check it again ...
- Davide
"A month of sundays ago Davide Libenzi wrote:"
Quoted 21 lines · Peter T. Breuer
Quoted 20 lines
No. This is not true. Imagine two threads, timed as follows ...
. . . .if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .(snl)->uniq = current; <-> if ((snl)->uniq == current) { atomic_inc(&(snl)->count); } else { spin_lock(&(snl)->lock); atomic_inc(&(snl)->count); (snl)->uniq = current;
Quoted 6 lines
Quoted 2 lines
There you are. One hits the read exactly at the time the other does a write. Bang.
So, what's bang for you ? The second task (the one that reads "uniq") will either see "uniq" as NULL or as (task1)->current. And it'll go acquiring the lock, as expected. Check it again ...
Perhaps I should expand on my earlier answer ...
(1) while, with some luck, writing may be atomic on ia32 (and I'm not sure it is, I'm only prepared to guarantee it for the lower bits, and I really don't know about zeroing the carry and so on), I actually doubt that reading is atomic, or we wouldn't need the atomic_read construction!
(2) I'm not prepared to bet that one either sees the answer from before the write was done, or the answer after it is done. I would suspect that one can get anything, including an explosion or reading of the works of tolstoy ...
(3) even if one gets either one or the other answer, one of them would be the wrong answer, and you clearly intend the atomic_inc of the counter to be done in the same atomic region as the setting to current, which would be a programming hypothesis that is broken when the wrong answer comes up.
Peter
Quoted 29 lines · Peter T. Breuer
"A month of sundays ago Davide Libenzi wrote:"
Quoted 21 lines · Peter T. Breuer
Quoted 20 lines
No. This is not true. Imagine two threads, timed as follows ...
. . . .if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .(snl)->uniq = current; <-> if ((snl)->uniq == current) { atomic_inc(&(snl)->count); } else { spin_lock(&(snl)->lock); atomic_inc(&(snl)->count); (snl)->uniq = current;Quoted 6 lines
Quoted 2 lines
There you are. One hits the read exactly at the time the other does a write. Bang.
So, what's bang for you ? The second task (the one that reads "uniq") will either see "uniq" as NULL or as (task1)->current. And it'll go acquiring the lock, as expected. Check it again ...
Quoted 7 lines
Perhaps I should expand on my earlier answer ...
(1) while, with some luck, writing may be atomic on ia32 (and I'm not sure it is, I'm only prepared to guarantee it for the lower bits, and I really don't know about zeroing the carry and so on), I actually doubt that reading is atomic, or we wouldn't need the
atomic_readconstruction!
Look at atomic read :
$ emacs `find /usr/src/linux/include -name atomic.h | xargs`
Quoted 5 lines
(3) even if one gets either one or the other answer, one of them would be the wrong answer, and you clearly intend the
atomic_incof the counter to be done in the same atomic region as the setting to current, which would be a programming hypothesis that is broken when the wrong answer comes up.
Atomic inc/dec/add/sub are different to read/write an aligned sizeof(int) memory location. An aligned sizeof(int) read/write must be atomic for the bare bone CPU memory coherency. While add/sub/add/inc are (or at least can be) split in MEMOP(load)->ALUOP(?)->MEMOP(store) whose full cycle is not guaranteed to be atomic, load/store of sizeof(int) aligned memory location are not split is every CPU whose designer was not drunk during the architectural phase. Or better, if they are split due some sort of HW limitation, the HW itself has to guarentee the atomicity of the operation. Intel tries also to guarantee the atomicity of non aligned load/store by doing split locks on the memory bus. If you have :
int a;
thread1:
for (;;) a = 1;
thread2:
for (;;) a = -1;
being "a" an aligned memory location, a third thread reading "a" reads either 1 or -1. Going back to the (doubtfully useful) code, you still have to point out were it does bang ...
- Davide
Quoted 9 lines
Quoted 5 lines
(1) while, with some luck, writing may be atomic on ia32 (and I'm not sure it is, I'm only prepared to guarantee it for the lower bits, and I really don't know about zeroing the carry and so on), I actually doubt that reading is atomic, or we wouldn't need the
atomic_readconstruction!Look at atomic read :
$ emacs `find /usr/src/linux/include -name atomic.h | xargs`
:-). Well, whaddya know. Both read and write of a int (declared volatile) are atomic on ia32.
Quoted 5 lines
Quoted 5 lines
(3) even if one gets either one or the other answer, one of them would be the wrong answer, and you clearly intend the
atomic_incof the counter to be done in the same atomic region as the setting to current, which would be a programming hypothesis that is broken when the wrong answer comes up.
[snip atomicity of read/write]
Quoted 3 lines
being "a" an aligned memory location, a third thread reading "a" reads either 1 or -1. Going back to the (doubtfully useful) code, you still have to point out were it does bang ...
OK. I'll have a look later.
Peter
Quoted 2 lines · Peter T. Breuer
:-). Well, whaddya know. Both read and write of a int (declared volatile) are atomic on ia32.
Except when they aren't. There are ppro SMP issues about ordering of unlocked stores in some situations. Thats why the PPro generates lock movb $0, foo for the unlock on PPro
Fixable however by PPro specific lock ops
"Davide Libenzi wrote:"
Quoted 16 lines · Peter T. Breuer
Quoted 14 lines
Quoted 14 lines
Quoted 14 lines
. . .if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .(snl)->uniq = current; <-> if ((snl)->uniq == current) { atomic_inc(&(snl)->count); } else { spin_lock(&(snl)->lock); atomic_inc(&(snl)->count); (snl)->uniq = current;
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
So, what's bang for you ? The second task (the one that reads "uniq") will either see "uniq" as NULL or as (task1)->current. And it'll go acquiring the lock, as expected. Check it again ...
Let's take that as hypothetically true.
Quoted 8 lines
Quoted 5 lines
(3) even if one gets either one or the other answer, one of them would be the wrong answer, and you clearly intend the
atomic_incof the counter to be done in the same atomic region as the setting to current, which would be a programming hypothesis that is broken when the wrong answer comes up.either 1 or -1. Going back to the (doubtfully useful) code, you still have to point out were it does bang ...
The "unexpected" sutuation is when the RH process reads the old value of uniq, just before the LH process sets it. Let's suppose that it erroneously reads NULL, since that's what was set last, at the unlock that lets the LH spinlock open up. That's OK, because it's not equal to its own task identifier either, and that's the only special thing it's looking for.
Umm ... actually, the RH process could read uniq before the LH process entered the spinlock. If it were at that time equal to its own task identifier, then chaos would ensue. But if it were so equal, then the RH process would have the spinlock, since it's taken before setting uniq. OK, I agree, there's no problem if the read doesn't blow up.
Peter
Actually, it is safe to have the concurrent/race condition for the read of a lock owner (outside the lock) and the write of a lock owner (inside the lock) as long as the "current owner" value stored inside the lock is "sent away" before the recursive lock is unlocked for the last time.
The owner value doesn't even have to be atomic (though it ought to be) The only "hard" requirement is that there is no mid-update value that can ever be somebody else. This requirement can be violated in some odd segmenting systems if "me" is a pointer. If me is a machine-primitive scalar the probability drops to nearly null that a partially written value can match anybody else (on an x86 platform, you toss a bus-lock around the assignment, which is what, I believe, the atomic type assignments do).
Since the logic reads "if not me then wait for lock else increment depth" you only have to guard against false positives. That guard case is accomplished by making sure you don't ever leave "yourself" in the owner slot when you free up the lock.
So generically:
get_lock():
if owner==me
then
++depth;
else
wait on actual lock primitive
possibly_atomic_assign(owner = me)
depth = 1
fi
free_lock()
/* optional debug test */
if owner != me
then
oops()
fi
if depth > 1
then
--depth
else
depth = 0
possibly_atomic_assign(owner = nobody)
release actual lock primitive
fi
There needs must be a "nobody" (a well defined quasi-legal value that can not occur in the legitimate set of owners, like -1 or NULL) assigned to the owner item so that you cannot encounter your own id in the owner slot when you don't actually have the lock primitive.
At several glances this structure seems odd and somehow vulnerable, but when you consider that a thread is never actually competing with itself, you get closure on the system. (that is, once you really internalize the fact that the same thread can not be multiply entrant on both of these routines at the same time, and you see that all other threads will do a proper wait on the "real" primitive lock because of conditional exclusion (e.g. they are not ever the owner at the time of the test, no matter how you update owner in the sequence, if they are, in fact, not the owner of the lock.)
Hitting the read and write at the same time is not a "bang" because (if the rest of the code is correct) the value being read, even if it is "trash" because of a partial update, will not let the reader into the "is me" part of the logic and the not-me branch is a wait for the "real" spinlock. Again, you might want to use atomic_read() and atomic_set(), then again, according to the headers you are only guaranteed 24 bits of atomic protection anyway, so if the owner is a pointer, it probably won't help that much.
The finer points include the fact that the depth and owner values are actually protected values inside the domain of the real lock primitive. They are just as safe as any other value protected by the lock. The inequality test "outside" the lock is actually a microcosm of the readers/writer kind of behavior. "Atomicizing" the owner value armors against the possibility of CPU reading a half-written value that "happens" to match the enquiring thread ID. But since the only transition that can occur is from some existent owner to "nobody", or from "nobody" to the new owner, a well chosen "nobody" can make the atomic assignment moot anyway.
I use this recursion layer all the time with posix mutex(es) in application layer code where I don't actually have an atomic_t to begin with.
It is actually provable.
Rob.
-----Original Message-----
From: [email protected] [mailto:[email protected]]On Behalf Of Peter T. Breuer
Sent: Sunday, May 18, 2003 4:15 PM
To: Davide Libenzi
Cc: [email protected]
Subject: Re: recursive spinlocks. Shoot.
Quoted 9 lines · In article <[email protected]> you wrote:
Quoted 7 lines
Quoted 4 lines
#define nestlock_lock(snl) \ do { \ if ((snl)->uniq == current) { \That would be able to read uniq while it is being written by something else (which it can, according to the code below). It needs protection.
No it does not, look better.
I'm afraid I only see that it does!
Quoted 11 lines
Quoted 8 lines
Quoted 5 lines
atomic_inc(&(snl)->count); \ } else { \ spin_lock(&(snl)->lock); \ atomic_inc(&(snl)->count); \ (snl)->uniq = current; \Hmm .. else we wait for the lock, and then set count and uniq, while somebody else may have entered and be reading it :-). You exit with
Nope, think about a case were it breaks. False negatives are not possible because it is set by the same task and false positives either.
No. This is not true. Imagine two threads, timed as follows ...
.
.
.
.if ((snl)->uniq == current) {
atomic_inc(&(snl)->count); .
} else { .
spin_lock(&(snl)->lock); .
atomic_inc(&(snl)->count); .
(snl)->uniq = current; <-> if ((snl)->uniq == current) {
atomic_inc(&(snl)->count);
} else {
spin_lock(&(snl)->lock);
atomic_inc(&(snl)->count);
(snl)->uniq = current;There you are. One hits the read exactly at the time the other does a write. Bang.
Quoted 8 lines
Quoted 3 lines
Well, it's not assembler either, but at least it's easily comparable with the nonrecursive version. It's essentially got an extra if and an inc in the lock. That's all.
Well, there's a little difference. In case of contention, you loop with your custom try lock while I used the optimized asm code inside
spin_lock. But again, I believe we didn't lose anything with the removal of this code (nested/recursive locks) from the kernel.
We lose hours of programmers time, looking for deadlocks caused by accidently taking the same spinlock twice and not knowing it.
A question in my mind is whether a fault in a third thread, like sleeping with a spinlock held, can make a recursive spinlock into a fault causer ... no, I don't see any way.
Peter
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/