Kernel RCU: shrink the size of the struct rcu_head
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
Quoted 9 lines · Mathieu Desnoyers
Hi Paul,
I noticed that you already discussed the possibility of shrinking the struct
rcu_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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
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_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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 torcu_defer_barrier_thread()which in turn callssynchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invokecall_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 theCPU_DYINGnotifier, 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
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_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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 torcu_defer_barrier_thread()which in turn callssynchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invokecall_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 asynchronize_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-sideC.S.. 1, 2, 3 are incompatible with read-sideC.S. context because they require to usesynchronize_rcu()within theC.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 withexit(). How does the kernelcall_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 allowcall_rcu()to be called from read-sideC.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 forcall_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 theCPU_DYINGnotifier, 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_DYINGexecution 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
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_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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 torcu_defer_barrier_thread()which in turn callssynchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invokecall_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 asynchronize_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-sideC.S.. 1, 2, 3 are incompatible with read-sideC.S. context because they require to usesynchronize_rcu()within theC.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 withexit(). How does the kernelcall_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. Socall_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 allowcall_rcu()to be called from read-sideC.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 forcall_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 theCPU_DYINGnotifier, 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_DYINGexecution 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
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_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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 torcu_defer_barrier_thread()which in turn callssynchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invokecall_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 asynchronize_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-sideC.S.. 1, 2, 3 are incompatible with read-sideC.S. context because they require to usesynchronize_rcu()within theC.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 withexit(). How does the kernelcall_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. Socall_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 allowcall_rcu()to be called from read-sideC.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()todefer_rcu()and removed the define forcall_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-sideC.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-sideC.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 forcall_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-sideC.S. could really be a problem here.This is why I think aving two interfaces, one permitting calling
call_rcu()from withinC.S., but requiring the added structrcu_head, and the other using per-thread queues with maximum size, rate limiting, but which cannot be used in read-sideC.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 theCPU_DYINGnotifier, 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_DYINGexecution 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 callrcu_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 9A68Signature · 2 lines
Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
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_headby 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.cimplementation, where I perform pointer encoding to compact the usual case, expected to be the same callback passed as parameter multiple times in a row tocall_rcu(). This is very typical with multiplefree()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 torcu_defer_barrier_thread()which in turn callssynchronize_rcu(). This is necessary to handle queue overflow. (Which appears to be why you introduce a new API, as it is legal to invokecall_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 asynchronize_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-sideC.S.. 1, 2, 3 are incompatible with read-sideC.S. context because they require to usesynchronize_rcu()within theC.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 withexit(). How does the kernelcall_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. Socall_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 allowcall_rcu()to be called from read-sideC.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()todefer_rcu()and removed the define forcall_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-sideC.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-sideC.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()anddefer_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_headin 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 forcall_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-sideC.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 withinC.S., but requiring the added structrcu_head, and the other using per-thread queues with maximum size, rate limiting, but which cannot be used in read-sideC.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 theCPU_DYINGnotifier, 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_DYINGexecution 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 callrcu_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 9A68Signature · 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