Re: array of pointers with rcu

[Michael S. Tsirkin]

On Sun, Jun 28, 2009 at 09:14:11AM -0700, Paul E. McKenney wrote:
> On Sun, Jun 28, 2009 at 04:22:24PM +0300, Michael S. Tsirkin wrote:
> > Paul,
> > I'd like to implement a static array of pointers with rcu.
> > (Note that Documentation/RCU/arrayRCU.txt addresses only the case of
> > static arrays where the data (rather than a pointer to the data) is
> > located in each array element).
> > The array is implemented today in kvm as follows:
> > 
> > struct kvm_io_bus {
> >         int                   dev_count;
> > #define NR_IOBUS_DEVS 6
> >         struct kvm_io_device *devs[NR_IOBUS_DEVS];
> > };
> > 
> > It's easy to use rcu_assign_pointer and
> > rcu_dereference to access each value in the array,
> > so that's fine.
> > 
> > However, I also have the dev_count value to handle.
> > This value is usually used in loops like this
> > 
> > for (i = 0; i < bus->dev_count; ++i) {
> > 	... uses bus->devs[i] ...
> > }
> 
> So the count can vary, then.  In other words, someone might change the
> value of ->dev_count from (say) 5 to (say) 2, implicitly invalidating
> the last three ->devs pointers, correct?
> 
> Of course, this implicit invalidation might happen just after you
> fetched the value of (say) ->devs[3].  Or just after you fetch the
> value of ->dev_count, for that matter.

Yes. So I need to be careful to call synchronize_rcu after changing dev_count
and before I can assume readers see an updated value.

> > I can assign the dev_count value with rcu_assign_pointer and even though
> > it is not a pointer I think it should work fine.  However, to access
> > dev_count I think that rcu_dereference will not do what I want:
> > 
> > #define rcu_dereference(p)     ({ \
> >                                 typeof(p) _________p1 = ACCESS_ONCE(p);
> > \
> >                                 smp_read_barrier_depends(); \
> >                                 (_________p1); \
> >                                 })
> > 
> > 
> > The use of dev_count is not through a dependency so
> > smp_read_barrier_depends will not be enough on most architectures.
> > 
> > So it seems that what I really need is something like:
> > #define rcu_read_value(p)     ({ \
> >                                 typeof(p) _________p1 = ACCESS_ONCE(p);
> > \
> >                                 smp_rmb(); \
> >                                 (_________p1); \
> >                                 })
> > 
> > And maybe
> > #define rcu_assign_value rcu_assign_pointer
> > for symmetry.
> > 
> > Comments?
> 
> Hmmm...
> 
> What you would really need to do in the above scheme is to make careful
> use of memory barriers trao order the accesses to ->dev_count and the the
> elements of the ->devs[] array.

Right, that's my plan. I think that the strategy I outlined above where
dev_count is always set with rcu_assign_value and read with
rcu_read_value, all array entries are read after dev_count is read with
rcu_dereference, and are assigned before dev count is updated with
rcu_assign_pointer will work in this case.

What I was thinking is that maybe this pattern is generic
enough to be of use to others. But maybe not.

> The usual trick to avoid such memory
> barriers it to dynamically allocate the array, but putting the count
> into a struct that includes the array, so that readers are guaranteed
> to get a value of ->dev_count that matches the ->devs[] array.
> 
> Of course, you might have other reasons for the array to be statically
> allocated.  In that case, one trick is to statically allocate two
> arrays, each with its own ->dev_count.  Then a size-change update will
> copy from the current array to the new array, set the value of the new
> ->dev_count appropriately, and then use rcu_assign_pointer() to cause
> new readers to see the updated array.  In short, use the approach
> described for resizeable arrays in Documentation/RCU/arrayRCU.txt
> even though the physical array stays the same size.
> 
> But again given that you only have six elements, why not just scan the
> whole array unconditionally, using NULL pointers in the ->devs[] elements
> to indicate that the corresponding element is invalid?  Then the normal
> rcu_assign_pointer() and rcu_dereference() will work normally.
> 
> 							Thanx, Paul


People are speaking about increasing the array size to 512. That's
a nice 4K page but adding the number of entries gets us just above that
which is kind of annoying.

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