Multi-threading
A message that is not in the archive (sent off-list or not yet received): 20020311182111Z310364-889+120750@vger.kernel.org.suse.lists.linux.kernel
Quoted 4 lines · Brad Pepers
there is a very complex multi-process dance involving (apparently) multiple debugger interactions per wake up. Kinda like the guys who designed the threads didn't talk to the guys who designed ptrace or one or the other didn't care.
I guess the new futex mechanism that is currently designed/debugged/discussed will take care of that. It doesn't require signals anymore. Unfortunately it is probably some time off until it can be used generally, but at least it is worked on
[the only problem i currently see in using futexes for pthread mutexes is that if there are really architectures that need a special mapping for them to work these won't be able to use them for this]
It is known that gdb is not the best thread debugger in the world :/
Quoted 6 lines
A second problem is implementing a use-count mechanism to control object lifetimes in a multi-threaded environment. The two alternatives are to use mutexes or other synchronization mechanisms to protect all addRef/release calls (very, very expensive) or to use interlocked increment/decrement mechanisms. Unfortunately, while Microsoft provides intrinsic
Quoted 8 lines
InterlockedIncrement/InterlockedDecrement functions that perform atomic multiprocessor interlocked operations that correctly return the result of the operation. Unfortunately, there are no such functions available on Linux.
Atomic.hprovides interlocked increment/decrement, but they don't return values. Interestingly enough, Google couldn't find any example of the Intel instruction sequences required to implement the necessary atomic operations using the GNU assembler dialect.
atomic_dec_and_test() ?
atomic_dec_and_return() doesn't strike me as too useful, because it would need to lie to you. When you have a reference count and you unlink the object first from public view you can trust a 0 check (as atomic_dec_and_test does). As long as the object is in public view someone else can change the counts and any "atomic return" of that would be just lying. You can of course always use atomic_read(), but it's not really atomic. I doubt the microsoft equivalent is atomic neither, they are probably equivalent to atomic_inc(); atomic_read(); or atomic_dec(); atomic_read() and some hand weaving.
BTW regarding atomic.h: while it is nicely usable on i386 in userspace it isn't completely portable. Some architectures require helper functions that are hard to implement in user space.
-Andi
Quoted 10 lines · Andi Kleen
Quoted 4 lines · Brad Pepers
there is a very complex multi-process dance involving (apparently) multiple debugger interactions per wake up. Kinda like the guys who designed the threads didn't talk to the guys who designed ptrace or one or the other didn't care.
I guess the new futex mechanism that is currently designed/debugged/discussed will take care of that. It doesn't require signals anymore. Unfortunately it is probably some time off until it can be used generally, but at least it is worked on
I'll watch the futex development than and wait for it do be available.
Quoted 1 line
atomic_dec_and_test()?
Handles the most common case but not general enough for all cases and its sister function atomic_inc_and_test is pretty useless.
Quoted 10 lines
atomic_dec_and_return()doesn't strike me as too useful, because it would need to lie to you. When you have a reference count and you unlink the object first from public view you can trust a 0 check (asatomic_dec_and_testdoes). As long as the object is in public view someone else can change the counts and any "atomic return" of that would be just lying. You can of course always useatomic_read(), but it's not really atomic. I doubt the microsoft equivalent is atomic neither, they are probably equivalent toatomic_inc();atomic_read(); oratomic_dec();atomic_read()and some hand weaving.
Apparently the Microsoft one really is in Windows 98 and up (not in 95). I've had it explained that the asm code (semi-pseudo code here) is like this:
movl reg, #-1
lock xadd reg, counter
decl reg
movl result, regThis is in comparison to the current code which does something like this:
lock decl counter
sete result
I don't see how the first asm code lies to you. It is returning the value as it was decremented to and the lock on the xadd keeps it safe.
Quoted 3 lines
BTW regarding
atomic.h: while it is nicely usable on i386 in userspace it isn't completely portable. Some architectures require helper functions that are hard to implement in user space.
Its too bad Linux didn't have a nice wrapper around atom inc/dec/test that was completely portable. Do you know what arch's have trouble implementing this?
Signature · 2 lines
Brad Pepers [email protected]
Quoted 19 lines · Brad Pepers
Quoted 10 lines
atomic_dec_and_return()doesn't strike me as too useful, because it would need to lie to you. When you have a reference count and you unlink the object first from public view you can trust a 0 check (asatomic_dec_and_testdoes). As long as the object is in public view someone else can change the counts and any "atomic return" of that would be just lying. You can of course always useatomic_read(), but it's not really atomic. I doubt the microsoft equivalent is atomic neither, they are probably equivalent toatomic_inc();atomic_read(); oratomic_dec();atomic_read()and some hand weaving.Apparently the Microsoft one really is in Windows 98 and up (not in 95). I've had it explained that the asm code (semi-pseudo code here) is like this:
movl reg, #-1 lock xadd reg, counter decl reg movl result, reg
Quoted 7 lines
This is in comparison to the current code which does something like this:
lock decl counter
sete resultI don't see how the first asm code lies to you. It is returning the value as it was decremented to and the lock on the xadd keeps it safe.
Just it might change immediately afterwards if you don't remove the object from public view first. An "atomic" value that you cannot depend on is not very useful. The Linux convention of using atomic_dec_and_test() is also only safe when you remove it first, but the dec_and_test encourages this at least. atomic_inc_and_read() could only be safe when you remove the object first too, but I don't see how it could be ever useful assuming you keep the convention that reference count == 0 means freeable object.
Quoted 8 lines
Quoted 4 lines
BTW regarding
atomic.h: while it is nicely usable on i386 in userspace it isn't completely portable. Some architectures require helper functions that are hard to implement in user space.Its too bad Linux didn't have a nice wrapper around atom inc/dec/test that was completely portable. Do you know what arch's have trouble implementing this?
sparc32 at least.
I think pa-risc32 too.
-Andi
Quoted 3 lines
Just it might change immediately afterwards if you don't remove the object from public view first.
If it was in public view, whatever held it in public view would be using it,
and hence its use count could not drop to zero.
DS
Quoted 6 lines · David Schwartz
Quoted 3 lines
Just it might change immediately afterwards if you don't remove the object from public view first.
If it was in public view, whatever held it in public view would be using it,
and hence its use count could not drop to zero.
That's not correct at least in the usual linux kernel pattern of using reference counts for objects. Hash tables don't hold reference counts, only users do. If you think about it a hash table or global list holding a reference count doesn't make too much sense.
-Andi
Quoted 8 lines · Andi Kleen
Quoted 3 lines
If it was in public view, whatever held it in public view would be using it,
and hence its use count could not drop to zero.That's not correct at least in the usual linux kernel pattern of using reference counts for objects. Hash tables don't hold reference counts, only users do. If you think about it a hash table or global list holding a reference count doesn't make too much sense.
That's the way I've always done it and it has saved me a lot of heartache. A
use count of 'zero' means that it's really not used at all, and hence nothing would have any way of finding it. Anything with a future interest in something should 'use' it.
In any event, hash tables require locks themselves anyway. So if you find an
object in a hash table, you must be holding some lock when you find it, so you can increment the use count under the protection of that lock. The trick becomes the decrement operation, because ideally you'd prefer not to have to lock the hash table again unless you have to remove the object.
I believe, however, that you are completely safe if you decrement the use
count atomically, and if it's zero, you grab the hash lock, confirm that the use count is still zero, and then remove the object.
Since the use count is always locked for the first time in any usage chain
with the hash lock held (lock it when you find it), an increment from zero to one can only occur while the lock is held. So if you hold the lock, an increment from zero to one cannot occur. No race.
DS
Quoted 5 lines · On Wed, 13 Mar 2002 09:23:06 +0100 Andi Kleen <[email protected]> wrote:
Quoted 4 lines · David Schwartz
Quoted 3 lines
Just it might change immediately afterwards if you don't remove the object from public view first.
Quoted 7 lines
Quoted 2 lines
If it was in public view, whatever held it in public view would be using it, and hence its use count could not drop to zero.
That's not correct at least in the usual linux kernel pattern of using reference counts for objects. Hash tables don't hold reference counts, only users do. If you think about it a hash table or global list holding a reference count doesn't make too much sense.
Depends where you are talking. In the conntrack code (and I thought the rest of the networking code), 0 means "free me now, NOONE has a pointer", ie. the hash table holds 1.
dcache holds zero-count entries because their semantic requirements are different, hence the "atomic_dec_and_lock()" stuff.
Cheers!
Rusty.
Signature · 1 line
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.