Re: Multi-threading

[David Schwartz <davids@webmaster.com>]

On Wed, 13 Mar 2002 09:23:06 +0100, Andi Kleen wrote:


>>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