Skip to contentSkip to conversation

Kernel RCU: shrink the size of the struct rcu_head

DISCUSSION Mathieu Desnoyers 2 participants 7 messages Oct 18, 2009 – Oct 23, 2009

lore
Share & tools
lore
#0 lore raw

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

I just thought I should tell you before you start looking at this issue further.

Thanks,

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#1 lore raw
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 6 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

Quoted 6 lines

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct? If I understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

Thanx, Paul

#2 lore raw
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 10 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

Quoted 5 lines
Quoted 2 lines

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct?

Yes, exactly.

Quoted 10 lines

If I
understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

When dealing with queue overflow, I figured we have 4 alternatives. Either:

1, 2, 3) We proceed to execution of {the single, all, thread local}
callback(s) on the spot after a synchronize_rcu().

4) We expand the queue by allocating more memory.

The idea of pointer encoding to save space could be used with any of 1, 2, 3, or 4. As you say, call_rcu() requires (4), because it tolerates being called from an rcu read-side C.S.. 1, 2, 3 are incompatible with read-side C.S. context because they require to use synchronize_rcu() within the C.S., which would deadlock on its calling context.

Now, there is a rationale for the choice of (3) in my urcu-defer implementation:

* It's how I can deal with memory full (-ENOMEM) without letting the system die with exit(). How does the kernel call_rcu() deal with this currently ? BUG_ON, WARN_ON ?

* It acts as a rate limiter for urcu_defer_queue(). Basically, if a thread starts enqueuing callbacks too fast, it will eventually fill its queue and have to empty it itself. AFAIK, It's not possible to do that if you allow call_rcu() to be called from read-side C.S..

I could even extend rcu_defer_queue() to take a second rate-limiter callback, which would check if the thread went over some threshold and give a more precise limit (e.g. amount of memory to be freed) on the rate than the "4096 callbacks in flight max", which have been chosen by benchmarks, but is a bit arbitrary in terms of overall callback effect.

How important is it to permit enqueuing callbacks from within rcu read-side C.S. in terms of real-life usage ? If it is really that important to fill this use-case, then I could have a mode for call_rcu() that expands the RCU callback queue upon overflow. But as I argue above, I really prefer the control we have with a fixed-sized queue.

Quoted 9 lines

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

As you say, we don't _have_ to empty the queue before putting a thread/cpu offline. We could simply copy the unplugged cpu queue to an orphan queue, as you currently do in your implementation. I agree that it would be more suitable to the cpu hotplug CPU_DYING execution context, due to its inherent trickiness.

Thanks,

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#3 lore raw
Quoted 24 lines · Mathieu Desnoyers
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 10 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct?

Yes, exactly.

OK, I will add something to this effect on my rcutodo page.

Quoted 25 lines
Quoted 10 lines

If I
understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

When dealing with queue overflow, I figured we have 4 alternatives. Either:

1, 2, 3) We proceed to execution of {the single, all, thread local}
callback(s) on the spot after a synchronize_rcu().

4) We expand the queue by allocating more memory.

The idea of pointer encoding to save space could be used with any of 1, 2, 3, or 4. As you say, call_rcu() requires (4), because it tolerates being called from an rcu read-side C.S.. 1, 2, 3 are incompatible with read-side C.S. context because they require to use synchronize_rcu() within the C.S., which would deadlock on its calling context.

Quoted 6 lines

Now, there is a rationale for the choice of (3) in my urcu-defer implementation:

* It's how I can deal with memory full (-ENOMEM) without letting the system die with exit(). How does the kernel call_rcu() deal with this currently ? BUG_ON, WARN_ON ?

It doesn't have to do anything -- the caller of call_rcu() is responsible for allocating any required memory. So call_rcu() never allocates memory and thus never needs to worry about a memory-allocation failure.

Quoted 4 lines

* It acts as a rate limiter for urcu_defer_queue(). Basically, if a thread starts enqueuing callbacks too fast, it will eventually fill its queue and have to empty it itself. AFAIK, It's not possible to do that if you allow call_rcu() to be called from read-side C.S..

Yep! ;-)

Quoted 11 lines

I could even extend rcu_defer_queue() to take a second rate-limiter callback, which would check if the thread went over some threshold and give a more precise limit (e.g. amount of memory to be freed) on the rate than the "4096 callbacks in flight max", which have been chosen by benchmarks, but is a bit arbitrary in terms of overall callback effect.

How important is it to permit enqueuing callbacks from within rcu read-side C.S. in terms of real-life usage ? If it is really that important to fill this use-case, then I could have a mode for call_rcu() that expands the RCU callback queue upon overflow. But as I argue above, I really prefer the control we have with a fixed-sized queue.

There are occurrences of this in the Linux kernel. In theory, you could always hang onto the object until leaving the outermost RCU read-side critical section, but in practice this is not always consistent with good software-engineering practice.

One use case is when you have an RCU-protected list, each element of which has an RCU-protected list hanging off it. In this case, you might scan the upper-level list under RCU protection, but during the scan you might need to remove elements from the lower-level list and pass them to call_rcu().

So it really needs to be legal for call_rcu() to be invoked from within an RCU read-side critical section.

Quoted 9 lines
Quoted 8 lines

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

Quoted 5 lines

As you say, we don't _have_ to empty the queue before putting a thread/cpu offline. We could simply copy the unplugged cpu queue to an orphan queue, as you currently do in your implementation. I agree that it would be more suitable to the cpu hotplug CPU_DYING execution context, due to its inherent trickiness.

Especially if you want something like rcu_barrier() to continue working.

Hmmm... Can user applications unload dynamically linked libraries? ;-)

Thanx, Paul

Quoted 10 lines

Thanks,

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#4 lore raw
Quoted 63 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 10 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct?

Yes, exactly.

OK, I will add something to this effect on my rcutodo page.

Quoted 28 lines
Quoted 10 lines

If I
understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

When dealing with queue overflow, I figured we have 4 alternatives. Either:

1, 2, 3) We proceed to execution of {the single, all, thread local}
callback(s) on the spot after a synchronize_rcu().

4) We expand the queue by allocating more memory.

The idea of pointer encoding to save space could be used with any of 1, 2, 3, or 4. As you say, call_rcu() requires (4), because it tolerates being called from an rcu read-side C.S.. 1, 2, 3 are incompatible with read-side C.S. context because they require to use synchronize_rcu() within the C.S., which would deadlock on its calling context.

Now, there is a rationale for the choice of (3) in my urcu-defer implementation:

Quoted 8 lines
Quoted 3 lines

* It's how I can deal with memory full (-ENOMEM) without letting the system die with exit(). How does the kernel call_rcu() deal with this currently ? BUG_ON, WARN_ON ?

It doesn't have to do anything -- the caller of call_rcu() is responsible for allocating any required memory. So call_rcu() never allocates memory and thus never needs to worry about a memory-allocation failure.

I see. So it puts the burden of memory allocation onto the creation of the original object we are dealing with. I understand why it's done like that now: it does not add another memory allocation failure point.

Quoted 8 lines
Quoted 4 lines

* It acts as a rate limiter for urcu_defer_queue(). Basically, if a thread starts enqueuing callbacks too fast, it will eventually fill its queue and have to empty it itself. AFAIK, It's not possible to do that if you allow call_rcu() to be called from read-side C.S..

Yep! ;-)

From userland point of view, it would be good to provide an API that

allows rate-limiting, especially to deal with DoS types of attacks. I I just renamed rcu_defer_queue() to defer_rcu() and removed the define for call_rcu(), because this last mapping introduced an API with the same name as the kernel API, but with different parameters.

So the idea is to have:

* defer_rcu(fct, p): fixed-sized queue rcu work deferral. Cannot be called from rcu read-side C.S..
* defer_rcu_ratelimit(fct, p, rl): same as above, but with added rate limiter callback.

and, eventually, to add back a standard call_rcu(), which can be called from within RCU read-side C.S., but which provides no rate limiting whatsoever.

Quoted 18 lines
Quoted 7 lines

I could even extend rcu_defer_queue() to take a second rate-limiter callback, which would check if the thread went over some threshold and give a more precise limit (e.g. amount of memory to be freed) on the rate than the "4096 callbacks in flight max", which have been chosen by benchmarks, but is a bit arbitrary in terms of overall callback effect.

Quoted 5 lines

How important is it to permit enqueuing callbacks from within rcu read-side C.S. in terms of real-life usage ? If it is really that important to fill this use-case, then I could have a mode for call_rcu() that expands the RCU callback queue upon overflow. But as I argue above, I really prefer the control we have with a fixed-sized queue.

There are occurrences of this in the Linux kernel. In theory, you could always hang onto the object until leaving the outermost RCU read-side critical section, but in practice this is not always consistent with good software-engineering practice.

Quoted 8 lines

One use case is when you have an RCU-protected list, each element of which has an RCU-protected list hanging off it. In this case, you might scan the upper-level list under RCU protection, but during the scan you might need to remove elements from the lower-level list and pass them to call_rcu().

So it really needs to be legal for call_rcu() to be invoked from within an RCU read-side critical section.

I agree that not being able to use call_rcu() from a read-side C.S. could really be a problem here.

This is why I think aving two interfaces, one permitting calling call_rcu() from within C.S., but requiring the added struct rcu_head, and the other using per-thread queues with maximum size, rate limiting, but which cannot be used in read-side C.S. seems like a good tradeoff.

Quoted 16 lines
Quoted 10 lines
Quoted 9 lines

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

Quoted 5 lines

As you say, we don't _have_ to empty the queue before putting a thread/cpu offline. We could simply copy the unplugged cpu queue to an orphan queue, as you currently do in your implementation. I agree that it would be more suitable to the cpu hotplug CPU_DYING execution context, due to its inherent trickiness.

Quoted 3 lines

Especially if you want something like rcu_barrier() to continue working.

Hmmm... Can user applications unload dynamically linked libraries? ;-)

Yes. With dlclose(). But I expect library developers to call rcu_defer_barrier() in their destructor if they have queued any work. (/me sneaks a README update in the git tree to that effect) ;)

Thanks,

Mathieu

Quoted 13 lines

Thanx, Paul

Quoted 10 lines

Thanks,

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#5 lore raw
Quoted 91 lines · Mathieu Desnoyers
Quoted 63 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 10 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct?

Yes, exactly.

OK, I will add something to this effect on my rcutodo page.

Quoted 28 lines
Quoted 10 lines

If I
understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

When dealing with queue overflow, I figured we have 4 alternatives. Either:

1, 2, 3) We proceed to execution of {the single, all, thread local}
callback(s) on the spot after a synchronize_rcu().

4) We expand the queue by allocating more memory.

The idea of pointer encoding to save space could be used with any of 1, 2, 3, or 4. As you say, call_rcu() requires (4), because it tolerates being called from an rcu read-side C.S.. 1, 2, 3 are incompatible with read-side C.S. context because they require to use synchronize_rcu() within the C.S., which would deadlock on its calling context.

Now, there is a rationale for the choice of (3) in my urcu-defer implementation:

Quoted 7 lines
Quoted 3 lines

* It's how I can deal with memory full (-ENOMEM) without letting the system die with exit(). How does the kernel call_rcu() deal with this currently ? BUG_ON, WARN_ON ?

It doesn't have to do anything -- the caller of call_rcu() is responsible for allocating any required memory. So call_rcu() never allocates memory and thus never needs to worry about a memory-allocation failure.

I see. So it puts the burden of memory allocation onto the creation of the original object we are dealing with. I understand why it's done like that now: it does not add another memory allocation failure point.

Quoted 6 lines
Quoted 4 lines

* It acts as a rate limiter for urcu_defer_queue(). Basically, if a thread starts enqueuing callbacks too fast, it will eventually fill its queue and have to empty it itself. AFAIK, It's not possible to do that if you allow call_rcu() to be called from read-side C.S..

Yep! ;-)

From userland point of view, it would be good to provide an API that allows rate-limiting, especially to deal with DoS types of attacks. I I just renamed rcu_defer_queue() to defer_rcu() and removed the define for call_rcu(), because this last mapping introduced an API with the same name as the kernel API, but with different parameters.

So the idea is to have:

Quoted 8 lines

* defer_rcu(fct, p): fixed-sized queue rcu work deferral. Cannot be called from rcu read-side C.S..
* defer_rcu_ratelimit(fct, p, rl): same as above, but with added rate limiter callback.

and, eventually, to add back a standard call_rcu(), which can be called from within RCU read-side C.S., but which provides no rate limiting whatsoever.

These sound to me like interesting experiments, but I strongly suggest publishing them as "experimental, may change" or whatever. One thing to keep in mind is that the rate-limiting should not be used in real-time applications. Alternatively, you could allow defer_rcu() and defer_rcu_ratelimit() to return failure if the callback could not be queued immediately. Not that figuring out what to do in the failure case is particularly attractive...

Of course, the memory savings will depend on the workload. The defer_rcu*() primitives eliminate the need for a struct rcu_head in each data structure, but requires that the per-CPU/task callback queues be present.

Quoted 26 lines
Quoted 17 lines
Quoted 11 lines

I could even extend rcu_defer_queue() to take a second rate-limiter callback, which would check if the thread went over some threshold and give a more precise limit (e.g. amount of memory to be freed) on the rate than the "4096 callbacks in flight max", which have been chosen by benchmarks, but is a bit arbitrary in terms of overall callback effect.

How important is it to permit enqueuing callbacks from within rcu read-side C.S. in terms of real-life usage ? If it is really that important to fill this use-case, then I could have a mode for call_rcu() that expands the RCU callback queue upon overflow. But as I argue above, I really prefer the control we have with a fixed-sized queue.

There are occurrences of this in the Linux kernel. In theory, you could always hang onto the object until leaving the outermost RCU read-side critical section, but in practice this is not always consistent with good software-engineering practice.

Quoted 8 lines

One use case is when you have an RCU-protected list, each element of which has an RCU-protected list hanging off it. In this case, you might scan the upper-level list under RCU protection, but during the scan you might need to remove elements from the lower-level list and pass them to call_rcu().

So it really needs to be legal for call_rcu() to be invoked from within an RCU read-side critical section.

Quoted 7 lines

I agree that not being able to use call_rcu() from a read-side C.S. could really be a problem here.

This is why I think aving two interfaces, one permitting calling call_rcu() from within C.S., but requiring the added struct rcu_head, and the other using per-thread queues with maximum size, rate limiting, but which cannot be used in read-side C.S. seems like a good tradeoff.

The defer_rcu() interfaces might work out quite well, but it would be good to see how they do in real life. ;-)

Quoted 15 lines
Quoted 15 lines
Quoted 14 lines
Quoted 8 lines

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

As you say, we don't _have_ to empty the queue before putting a thread/cpu offline. We could simply copy the unplugged cpu queue to an orphan queue, as you currently do in your implementation. I agree that it would be more suitable to the cpu hotplug CPU_DYING execution context, due to its inherent trickiness.

Quoted 7 lines
Quoted 3 lines

Especially if you want something like rcu_barrier() to continue working.

Hmmm... Can user applications unload dynamically linked libraries? ;-)

Yes. With dlclose(). But I expect library developers to call rcu_defer_barrier() in their destructor if they have queued any work. (/me sneaks a README update in the git tree to that effect) ;)

;-)

Thanx, Paul

Quoted 21 lines

Thanks,

Mathieu

Quoted 13 lines

Thanx, Paul

Quoted 10 lines

Thanks,

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#6 lore raw
Quoted 109 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 91 lines · Mathieu Desnoyers
Quoted 63 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 23 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers

Hi Paul,

I noticed that you already discussed the possibility of shrinking the struct rcu_head by removing the function pointer.
(http://kernel.org/pub/linux/kernel/people/paulmck/rcutodo.html)

The ideas brought in so far require having per-callback lists, which involves a bit of management overhead and don't permit keeping the call_rcu() in cpu order.

But please note that this is on the "Possibly Dubious Changes" list. ;-)

Quoted 10 lines

You might want to look into the Userspace RCU urcu-defer.c implementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row to call_rcu(). This is very typical with multiple free() calls for different data structures next to each other.

This typically keeps the size of the information to encode per callback down to a minimum: the size of a single pointer. It would be good to trace the kernel usage of call_rcu() to see if my assumption holds.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

I just thought I should tell you before you start looking at this issue further.

So the idea is to maintain a per-CPU queue of function pointers, but with the pointers on this queue encoded to save space, correct?

Yes, exactly.

OK, I will add something to this effect on my rcutodo page.

Quoted 28 lines
Quoted 10 lines

If I
understand correctly, the user-level rcu-defer implementation relies on the following:

1. It is illegal to call _rcu_defer_queue() within an RCU read-side
critical section (due to the call to rcu_defer_barrier_thread() which in turn calls synchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invoke call_rcu() from within an RCU read-side critical section.)

When dealing with queue overflow, I figured we have 4 alternatives. Either:

1, 2, 3) We proceed to execution of {the single, all, thread local}
callback(s) on the spot after a synchronize_rcu().

4) We expand the queue by allocating more memory.

The idea of pointer encoding to save space could be used with any of 1, 2, 3, or 4. As you say, call_rcu() requires (4), because it tolerates being called from an rcu read-side C.S.. 1, 2, 3 are incompatible with read-side C.S. context because they require to use synchronize_rcu() within the C.S., which would deadlock on its calling context.

Now, there is a rationale for the choice of (3) in my urcu-defer implementation:

Quoted 7 lines
Quoted 3 lines

* It's how I can deal with memory full (-ENOMEM) without letting the system die with exit(). How does the kernel call_rcu() deal with this currently ? BUG_ON, WARN_ON ?

It doesn't have to do anything -- the caller of call_rcu() is responsible for allocating any required memory. So call_rcu() never allocates memory and thus never needs to worry about a memory-allocation failure.

I see. So it puts the burden of memory allocation onto the creation of the original object we are dealing with. I understand why it's done like that now: it does not add another memory allocation failure point.

Quoted 6 lines
Quoted 4 lines

* It acts as a rate limiter for urcu_defer_queue(). Basically, if a thread starts enqueuing callbacks too fast, it will eventually fill its queue and have to empty it itself. AFAIK, It's not possible to do that if you allow call_rcu() to be called from read-side C.S..

Yep! ;-)

From userland point of view, it would be good to provide an API that allows rate-limiting, especially to deal with DoS types of attacks. I I just renamed rcu_defer_queue() to defer_rcu() and removed the define for call_rcu(), because this last mapping introduced an API with the same name as the kernel API, but with different parameters.

So the idea is to have:

Quoted 8 lines

* defer_rcu(fct, p): fixed-sized queue rcu work deferral. Cannot be called from rcu read-side C.S..
* defer_rcu_ratelimit(fct, p, rl): same as above, but with added rate limiter callback.

and, eventually, to add back a standard call_rcu(), which can be called from within RCU read-side C.S., but which provides no rate limiting whatsoever.

These sound to me like interesting experiments, but I strongly suggest publishing them as "experimental, may change" or whatever. One thing to keep in mind is that the rate-limiting should not be used in real-time applications. Alternatively, you could allow defer_rcu() and defer_rcu_ratelimit() to return failure if the callback could not be queued immediately. Not that figuring out what to do in the failure case is particularly attractive...

Quoted 4 lines

Of course, the memory savings will depend on the workload. The defer_rcu*() primitives eliminate the need for a struct rcu_head in each data structure, but requires that the per-CPU/task callback queues be present.

Yep. Will mark rcu_defer() as experimental.

Quoted 30 lines
Quoted 30 lines
Quoted 18 lines
Quoted 7 lines

I could even extend rcu_defer_queue() to take a second rate-limiter callback, which would check if the thread went over some threshold and give a more precise limit (e.g. amount of memory to be freed) on the rate than the "4096 callbacks in flight max", which have been chosen by benchmarks, but is a bit arbitrary in terms of overall callback effect.

Quoted 5 lines

How important is it to permit enqueuing callbacks from within rcu read-side C.S. in terms of real-life usage ? If it is really that important to fill this use-case, then I could have a mode for call_rcu() that expands the RCU callback queue upon overflow. But as I argue above, I really prefer the control we have with a fixed-sized queue.

There are occurrences of this in the Linux kernel. In theory, you could always hang onto the object until leaving the outermost RCU read-side critical section, but in practice this is not always consistent with good software-engineering practice.

Quoted 8 lines

One use case is when you have an RCU-protected list, each element of which has an RCU-protected list hanging off it. In this case, you might scan the upper-level list under RCU protection, but during the scan you might need to remove elements from the lower-level list and pass them to call_rcu().

So it really needs to be legal for call_rcu() to be invoked from within an RCU read-side critical section.

I agree that not being able to use call_rcu() from a read-side C.S. could really be a problem here.

Quoted 7 lines
Quoted 4 lines

This is why I think aving two interfaces, one permitting calling call_rcu() from within C.S., but requiring the added struct rcu_head, and the other using per-thread queues with maximum size, rate limiting, but which cannot be used in read-side C.S. seems like a good tradeoff.

The defer_rcu() interfaces might work out quite well, but it would be good to see how they do in real life. ;-)

Indeed, usage will tell.

Thanks,

Mathieu

Quoted 49 lines
Quoted 16 lines
Quoted 16 lines
Quoted 15 lines
Quoted 9 lines

2. It is OK to wait for a grace period when a thread calls
rcu_defer_unregister_thread() while exiting. In the kernel, this is roughly equivalent to the CPU_DYING notifier, which cannot block, thus cannot wait for a grace period.

I could imagine copying the per-CPU buffer somewhere, though my experience with the RCU/CPU-hotplug interface does not encourage me in this direction. ;-)

As you say, we don't _have_ to empty the queue before putting a thread/cpu offline. We could simply copy the unplugged cpu queue to an orphan queue, as you currently do in your implementation. I agree that it would be more suitable to the cpu hotplug CPU_DYING execution context, due to its inherent trickiness.

Quoted 7 lines
Quoted 3 lines

Especially if you want something like rcu_barrier() to continue working.

Hmmm... Can user applications unload dynamically linked libraries? ;-)

Yes. With dlclose(). But I expect library developers to call rcu_defer_barrier() in their destructor if they have queued any work. (/me sneaks a README update in the git tree to that effect) ;)

;-)

Thanx, Paul

Quoted 21 lines

Thanks,

Mathieu

Quoted 13 lines

Thanx, Paul

Quoted 10 lines

Thanks,

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68