array of pointers with rcu

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] ...
}

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?

Quoted 17 lines · Michael S. Tsirkin

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.

Quoted 6 lines

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.

Quoted 27 lines

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.

Quoted 1 line

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.

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

Quoted 29 lines · Paul E. McKenney

Quoted 17 lines · Michael S. Tsirkin

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.

Quoted 6 lines

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?

Quoted 3 lines

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.

Quoted 27 lines

Quoted 27 lines

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.

Quoted 7 lines

Quoted 1 line

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.

Quoted 14 lines

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.

Quoted 4 lines

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.

Quoted 30 lines · Michael S. Tsirkin

Quoted 29 lines · Paul E. McKenney

Quoted 17 lines · Michael S. Tsirkin

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.

Quoted 6 lines

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?

Quoted 6 lines

Quoted 3 lines

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

Quoted 35 lines

Quoted 27 lines

Quoted 27 lines

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.

Quoted 7 lines

Quoted 1 line

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.

Quoted 8 lines

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.

Quoted 14 lines

Quoted 14 lines

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.

Quoted 8 lines

Quoted 4 lines

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