Re: [RFC] Refcounting of objects part of a lockfree collection

[Ravikiran G Thirumalai]

On Wed, Jul 14, 2004 at 12:07:00AM -0700, Greg KH wrote:
> On Wed, Jul 14, 2004 at 10:23:50AM +0530, Ravikiran G Thirumalai wrote:
> > 
> > The attatched patch provides infrastructure for refcounting of objects
> > in a rcu protected collection.
> 
> This is really close to the kref implementation.  Why not just use that
> instead?

Close, but not the same.  I just had a quick look at krefs.
Actually, this refrerence count infrastructure I am proposing is not for 
traditional refcounting.  This is for refcounting of elemnts of a list
or array (collection) which can be 'read' in a lock free manner.

For ex. With traditional refcounting, you can have 

1.                                  2.
add()                               search_and_reference()
{                                   {
    alloc_object                            read_lock(&list_lock);
    ...                                     search_for_element
    refcount_init(&el->rc)                  refcount_get(&el->rc);
    write_lock(&list_lock);                 ...
    add_element                             read_unlock(&list_lock);
    ...                                     ...
    write_unlock(&list_lock);       }
}

3.                                  4.
release_referenced()                delete()
{                                   {
    ...                             write_lock(&list_lock);
    if (refcount_put(&el->rc))      ...
            start_cleanup_object    ...
            free_object             delete_element
    ...                             write_unlock(&list_lock);
}                                   ...
                                    if (refcount_put(&el->rc))
                                            start_cleanup_object
                                            free_object
                                    }

add() puts the refcounted element into the system with the list_lock
taken for write, search_and_reference() takes the list_lock for read
and gets the refcount.  Now if the list was a read mostly kind, then
we could replace the list_lock rw lock with a spinlock,
serialise updates to the list with the spinlock taken (in the add())
and use rcu_read_lock() and rcu_read_unlock() on the reader side
(search_and_reference()) replacing the read_locks in 2. above. 

But, with rcu, search and reference could see stale elements, that is
elements which have been taken off the list from delete(). Using call_rcu
to free the object from release_referenced() (free_object in 3.) will defer 
freeing, so that &el memory location above is not freed 'til the reader 
comes out of rcu_read_lock protected code, _but_ the 
search_and_reference thread could potentially get a reference to a 
deleted list element.  Hence, under lockfree circumstances, just an 
atomic_inc to the refcount is not sufficient.  
We do:

	...
	c = atomic_read(&rc->count);
	while ( c && (old = cmpxchg(&rc->count.counter, c, c+1)) != c)
		c = old;
	return c;


which is abstracted out as refcount_get_rcu()

Hence, in the example above, search_and_reference would look like

search_and_reference()
{
    rcu_read_lock();
    search_for_element
    if (!refcount_get_rcu(&el->rc)) {
            rcu_read_unlock();
            return FAIL;
    }
    ...
    ...
    rcu_read_unlock();
}

Hope that clears things up.

> 
> Oh, and I think you need to use atomic_set() instead of initializing the
> atomic_t by hand.

I have used atomic_set for the case where arch has cmpxchg.  But for 
arches lacking cmpxchg, I need to use hashed spinlocks to implement 
the ref_count_get_rcu.
No point in having more atomic operations when I hold spinlocks.  Admittedly,
might be a bit yucky to assume atomic_t internals, but it is just one header
file :) <ducks>

Thanks,
Kiran
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/