Re: array of pointers with rcu

[Michael S. Tsirkin]

On Sun, Jun 28, 2009 at 02:10:41PM -0700, Paul E. McKenney wrote:
> On Sun, Jun 28, 2009 at 10:06:36PM +0300, Michael S. Tsirkin wrote:
> > 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.
> 
> Yep!!!

OK, thanks Paul.

> > > > 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.
> 
> This pattern has appeared a number of times, including in one of the
> first uses of RCU (for SysV IPC), but it has always eventually been turned
> into something that associates the array size with the array itself.
> 
> > > 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.
> > 
> > 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.
> 
> OK, 512 is large enough that just unconditionally scanning the array
> would not be a good plan.  ;-)
> 
> So, how about two arrays, each with count associated with it, and
> switching back and forth between them?  That way readers simply pick
> up the pointer to the current array/count, and are guaranteed that
> the count matches the array.
> 
> 							Thanx, Paul

Yes, that can work, too.

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