2.4.10pre7aa1
Subsystems (8)
Quoted 11 lines · In article <[email protected]> you wrote:
Quoted 8 lines · On Mon, 10 Sep 2001 17:54:17 +0200 Andrea Arcangeli <[email protected]> wrote:
Only in 2.4.10pre7aa1: 00_rcu-1
wait_for_rcuandcall_rcuimplementation (from IBM). I did some modifications with respect to the original version from IBM. In particular I dropped the vmalloc_rcu/kmalloc_rcu, thercu_headmust always be allocated in the data structures, it has to be a field of a class, rather than hiding it in the allocation and playing dirty and risky with casts on a bigger allocation.
Quoted 3 lines
Hi Andrea,
Like the kernel threads approach, but AFAICT it won't work for the case of two CPUs running
wait_for_rcuat the same time (on a 4-way or above).
The patch I submitted to Andrea had logic to make sure that two CPUs don't execute wait_for_rcu() at the same time. Somehow it seems to have got lost in Andrea's modifications.
I will look at that and submit a new patch to Andrea, if necessary.
As for wrappers, I am agnostic. However, I think sooner or later people will start asking for them, if we go by our past experience.
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.
Quoted 12 lines · Dipankar Sarma
Quoted 10 lines · In article <[email protected]> you wrote:
Quoted 8 lines · On Mon, 10 Sep 2001 17:54:17 +0200 Andrea Arcangeli <[email protected]> wrote:
Only in 2.4.10pre7aa1: 00_rcu-1
wait_for_rcuandcall_rcuimplementation (from IBM). I did some modifications with respect to the original version from IBM. In particular I dropped the vmalloc_rcu/kmalloc_rcu, thercu_headmust always be allocated in the data structures, it has to be a field of a class, rather than hiding it in the allocation and playing dirty and risky with casts on a bigger allocation.
Quoted 3 lines
Quoted 3 lines
Hi Andrea,
Like the kernel threads approach, but AFAICT it won't work for the case of two CPUs running
wait_for_rcuat the same time (on a 4-way or above).
Good catch!
As for your alternate approch patch I've a few comments:
1) there maybe an RT tasks running, shrinking ram without reschedules in between (ignore the current page_alloc that does a bogus schedule before starting memory balancing), so schedule may never run and the RT task can run oom, so you should at least set need_resched of the interesting cpus + send the IPI reschedule before returning from call_rcu to avoid to be starved
2) the real design issue here if we should pay 8k per-cpu and zero cpu cost for the fast paths, or if we want to pay with a new branch in schedule() fast path, I preferred the krcud approch for that reason:
+ if (atomic_read(&rcu_pending))
+ goto rcu_process;
+rcu_process_back:
Quoted 3 lines
The patch I submitted to Andrea had logic to make sure that two CPUs don't execute
wait_for_rcu()at the same time. Somehow it seems to have got lost in Andrea's modifications.
I think the bug was in your original patch too, I'm pretty sure I didn't broke anything while changing the API a little.
Quoted 1 line
I will look at that and submit a new patch to Andrea, if necessary.
I prefer to allow all cpus to enter wait_for_rcu at the same time rather than putting a serializing semaphore around wait_for_rcu (it should scale pretty well if we don't serialize around wait_for_rcu).
The way I prefer to fix it is just to replace the rcu_sema with a per-cpu semaphore and have wait_for_rcu running down on such per-cpu semaphore of the interesting cpu, should be a few liner patch (we have space free for it in the per-cpu rcu_data cacheline).
Quoted 2 lines
As for wrappers, I am agnostic. However, I think sooner or later people will start asking for them, if we go by our past experience.
Maybe I'm missing something but what's the problem in allocating the struct rcu_head in the data structure? I don't think it's not much more complicated than the cast magics, and in general I prefer to avoid casts on larger buffers to get advantage of the C compile time sanity checking ;).
Andrea
Quoted 3 lines · Andrea Arcangeli
Quoted 1 line
Quoted 1 line
Like the kernel threads approach, but AFAICT it won't work for the case of two CPUs running
wait_for_rcuat the same time (on a 4-way or above).Good catch!
It barfs on our 4way with the FD management patch and chat benchmark :-)
Quoted 6 lines
Quoted 3 lines
The patch I submitted to Andrea had logic to make sure that two CPUs don't execute
wait_for_rcu()at the same time. Somehow it seems to have got lost in Andrea's modifications.I think the bug was in your original patch too, I'm pretty sure I didn't broke anything while changing the API a little.
You changed the way I maintained the wait_list and current_list. The basic logic was that new callbacks are always added to the wait list. The wait_for_rcu() is started only if current_list was empty and we just moved the wait_list to current_list. The key step was moving the wait_list to current_list *after* doing a wait_for_rcu(). This prevents another CPU from doing a wait_for_rcu(). Either that or I missed something big time :-)
Quoted 6 lines
Quoted 2 lines
I will look at that and submit a new patch to Andrea, if necessary.
I prefer to allow all cpus to enter
wait_for_rcuat the same time rather than putting a serializing semaphore aroundwait_for_rcu(it should scale pretty well if we don't serialize aroundwait_for_rcu).
Serializing is not what I want to do either. Instead the other CPUs just add to the wait_list and return if there is a wait_for_rcu() going on. What we have seen is that relatively larger batches around a single recurring wait_for_rcu() will do reasonably well in terms of performance.
Quoted 5 lines
The way I prefer to fix it is just to replace the
rcu_semawith a per-cpu semaphore and havewait_for_rcurunning down on such per-cpu semaphore of the interesting cpu, should be a few liner patch (we have space free for it in the per-cpurcu_datacacheline).
It should be possible to do this. However, I am not sure we would really benefit significantly from allowing multiple wait_for_rcu()s to run parallelly. I would much rather see per-CPU lists implemented and avoid keventd eventually.
Quoted 8 lines
Quoted 3 lines
As for wrappers, I am agnostic. However, I think sooner or later people will start asking for them, if we go by our past experience.
Maybe I'm missing something but what's the problem in allocating the struct
rcu_headin the data structure? I don't think it's not much more complicated than the cast magics, and in general I prefer to avoid casts on larger buffers to get advantage of the C compile time sanity checking ;).
One disadvantage of the wrappers is that we would be wasting most of the L1 cache line for rcu_head and that could be relatively significant for a small frequently allocated structure. And no, I don't see any problem asking people to allocate the rcu_head in the data structure.
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.
Quoted 7 lines · Dipankar Sarma
You changed the way I maintained the
wait_listandcurrent_list. The basic logic was that new callbacks are always added to the wait list. Thewait_for_rcu()is started only ifcurrent_listwas empty and we just moved thewait_listtocurrent_list. The key step was moving thewait_listtocurrent_list*after* doing await_for_rcu(). This prevents another CPU from doing await_for_rcu(). Either that or I missed something big time :-)
Really when Rusty said "multiple cpus calling wait_for_rcu" I was thinking at common code calling wait_for_rcu directly (in such a case you would have a problem too), I thought it was exported as well as call_rcu.
If you mean races with call_rcu they cannot be explained by wait_for_rcu called by different cpus also with my approch because there's only one keventd so only one wait_for_rcu can run at once with my current code (obviously, only keventd will ever recall wait_for_rcu).
The problem should be elsewhere.
Also we still don't address the case of keventd being starved by RT tasks. Maybe we should just make keventd RT, but then it would hang if somebody reinserts itself for a long time :(. Maybe Russel's approch is the cleaner after all, it just adds a branch in schedule fast path but (once fixed properly with the IPI and need_resched and dropping the unused irq checks that we don't want anyways to avoid even further slowdown of the slow paths) then the other issues goes away as well as the memory consumation.
Quoted 4 lines
One disadvantage of the wrappers is that we would be wasting most of the L1 cache line for
rcu_headand that could be relatively significant for a small frequently allocated structure. And no, I don't see any problem asking people to allocate thercu_headin the data structure.
Ok. As usual people should care to order the fields in cacheline optimized manner, so for example they should care to put the rcu_head at the very end if they want to reserve the cacheline for the "hot" fields. This can infact save a cacheline if the data structure is very small. It's something we cannot choose in rcu_kmalloc etc... only the user can.
Andrea
In message <[email protected]> you write:
Quoted 6 lines
somebody reinserts itself for a long time :(. Maybe Russel's approch is the cleaner after all, it just adds a branch in schedule fast path but (once fixed properly with the IPI and
need_reschedand dropping the unused irq checks that we don't want anyways to avoid even further slowdown of the slow paths) then the other issues goes away as well as the memory consumation.
IPI and need_resched? That's incredibly heavy: why do you want to add this? Real-time tasks still call schedule() every so often, so I don't understand your aim here...
Quoted 3 lines
Ok. As usual people should care to order the fields in cacheline optimized manner, so for example they should care to put the
rcu_headat the very end if they want to reserve the cacheline for the "hot" fields.
Agreed. Added a new field to rcu_head, and hence a new arg to call_rcu(), so now you do things like:
call_rcu(&myfoo->rcu, kfree, &myfoo);
Other changes:
Added synchronize_kernel(), which is useful for module unload. Architectures which don't enter schedule() in idle loop check rcu. Optimizations for uniprocessor.
RCU callbacks are allowed to sleep.
Cheers,
Rusty.
--
Premature optmztion is rt of all evl. --DK
include/linux/rcupdate.h +51 -0
@@ -0,0 +1,51 @@ +#ifndef _LINUX_RCUPDATE_H +#define _LINUX_RCUPDATE_H +/* Read-Copy-Update For Linux. */ +#include <linux/config.h> +#include <asm/atomic.h> + +#ifdef CONFIG_SMP +struct rcu_head +{ +struct rcu_head *next; +void (*func)(void *data); +void *data; +}; + +/* Queues future request may sleep (if caller can sleep: on UP is +called immediately). */ +void call_rcu (struct rcu_head *head,void (*func)(void *data),void *data); + +/* Count of pending requests: for optimization in schedule() */ +extern atomic_t rcu_pending; +static inline int is_rcu_pending (void ) +{ +return atomic_read (&num_rcu_pending) !=0 ; +} + +/* Wait for every CPU to have moved on. Sleeps. */ +void synchronize_kernel (void ); + +#else /* !SMP */ + +/* Remember the good old days when we didn't have to worry about more +than one processor? */ +struct rcu_head { }; + +#define is_rcu_pending () 0 + +static inline void call_rcu (struct rcu_head *head, +void (*func)(void *data), +void *data) +{ +func (data); +} + +static inline void synchronize_kernel (void ) +{ +} +#endif /*CONFIG_SMP*/ + +/* Called by schedule() when batch reference count drops to zero. */ +void rcu_batch_done (void ); +#endif
kernel/Makefile +2 -2
@@ -9,12 +9,12 @@ O_TARGET := kernel.o -export-objs = signal.o sys.o kmod.o context.o ksyms.o pm.o +export-objs = signal.o sys.o kmod.o context.o ksyms.o pm.o rcupdate.o obj-y = sched.o dma.o fork.o exec_domain.o panic.o printk.o \ module.o exit.o itimer.o info.o time.o softirq.o resource.o \ sysctl.o acct.o capability.o ptrace.o timer.o user.o \ - signal.o sys.o kmod.o context.o + signal.o sys.o kmod.o context.o rcupdate.o obj-$(CONFIG_UID16) += uid16.o obj-$(CONFIG_MODULES) += ksyms.o
kernel/rcupdate.c +99 -0
99 lines not on this page · raw message
kernel/sched.c +25 -1
@@ -26,6 +26,7 @@#include <linux/interrupt.h> #include <linux/kernel_stat.h> #include <linux/completion.h> +#include <linux/rcupdate.h> #include <asm/uaccess.h> #include <asm/mmu_context.h>
@@ -99,12 +100,15 @@struct schedule_data {struct task_struct * curr;cycles_t last_schedule; +int ring_count, finished_count; } schedule_data;char __pad [SMP_CACHE_BYTES ]; -} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}}; +} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0,0,0}}};#define cpu_curr (cpu) aligned_data[(cpu)].schedule_data.curr#define last_schedule (cpu) aligned_data[(cpu)].schedule_data.last_schedule +#define ring_count (cpu) aligned_data[(cpu)].schedule_data.ring_count +#define finished_count (cpu) aligned_data[(cpu)].schedule_data.finished_countstruct kernel_stat kstat;
@@ -544,6 +548,10 @@release_kernel_lock (prev, this_cpu); +if (is_rcu_pending ()) + goto rcu_process; +rcu_process_back: +/* * 'sched_data' is protected by the fact that we can run * only one process per CPU.
@@ -693,6 +701,22 @@ c =goodness (prev, this_cpu, prev->active_mm); next = prev; goto still_running_back; + +rcu_process: +/* Avoid cache line effects if value hasn't changed */ + c =ring_count ((this_cpu +1 ) % smp_num_cpus) +1 ; +if (c !=ring_count (this_cpu)) { +/* Do subtraction to avoid int wrap corner case */ +if (c -finished_count (this_cpu) >=0 ) { +/* Avoid reentry: temporarily set finish_count +far in the future */ +finished_count (this_cpu) = c +INT_MAX ; +rcu_batch_done (); +finished_count (this_cpu) = c + smp_num_cpus; + } +ring_count (this_cpu) = c; + } + goto rcu_process_back; move_rr_last:if (!prev->counter) {
arch/alpha/kernel/process.c +3 -1
@@ -30,6 +30,7 @@#include <linux/reboot.h> #include <linux/tty.h> #include <linux/console.h> +#include <linux/rcupdate.h> #include <asm/reg.h> #include <asm/uaccess.h>
@@ -86,7 +87,8 @@get into the scheduler unnecessarily. */ long oldval =xchg (¤t->need_resched,-1UL );if (!oldval) -while (current->need_resched <0 ); +while (current->need_resched <0 + && !is_rcu_pending ());schedule ();check_pgt_cache (); }
arch/arm/kernel/process.c +2 -1
@@ -23,6 +23,7 @@#include <linux/reboot.h> #include <linux/interrupt.h> #include <linux/init.h> +#include <linux/rcupdate.h> #include <asm/system.h> #include <asm/io.h>
@@ -92,7 +93,7 @@if (!idle) idle = arch_idle;leds_event (led_idle_start); -while (!current->need_resched) +while (!current->need_resched && !is_rcu_pending ())idle ();leds_event (led_idle_end);schedule ();
arch/i386/kernel/process.c +2 -1
@@ -33,6 +33,7 @@#include <linux/reboot.h> #include <linux/init.h> #include <linux/mc146818rtc.h> +#include <linux/rcupdate.h> #include <asm/uaccess.h> #include <asm/pgtable.h>
@@ -131,7 +132,7 @@void (*idle)(void ) = pm_idle;if (!idle) idle = default_idle; -while (!current->need_resched) +while (!current->need_resched && !is_rcu_pending ())idle ();schedule ();check_pgt_cache ();
arch/ia64/kernel/process.c +2 -1
@@ -17,6 +17,7 @@#include <linux/smp_lock.h> #include <linux/stddef.h> #include <linux/unistd.h> +#include <linux/rcupdate.h> #include <asm/delay.h> #include <asm/efi.h>
@@ -121,7 +122,7 @@if (!current->need_resched)min_xtp ();#endif -while (!current->need_resched) +while (!current->need_resched && !is_rcu_pending ())continue ;#ifdef CONFIG_SMP normal_xtp ();
arch/mips/kernel/process.c +2 -1
@@ -19,6 +19,7 @@#include <linux/sys.h> #include <linux/user.h> #include <linux/a.out.h> +#include <linux/rcupdate.h> #include <asm/bootinfo.h> #include <asm/cpu.h>
@@ -40,7 +41,7 @@init_idle ();while (1 ) { -while (!current->need_resched) +while (!current->need_resched && !is_rcu_pending ())if (cpu_wait) (*cpu_wait)();schedule ();
arch/mips64/kernel/process.c +2 -1
@@ -18,6 +18,7 @@#include <linux/sys.h> #include <linux/user.h> #include <linux/a.out.h> +#include <linux/rcupdate.h> #include <asm/bootinfo.h> #include <asm/pgtable.h>
@@ -36,7 +37,7 @@ current->nice =20 ; current->counter =-100 ;while (1 ) { -while (!current->need_resched) +while (!current->need_resched && !is_rcu_pending ())if (wait_available) __asm__("wait" );schedule ();
arch/parisc/kernel/process.c +2 -1
@@ -26,6 +26,7 @@#include <linux/init.h> #include <linux/version.h> #include <linux/elf.h> +#include <linux/rcupdate.h> #include <asm/machdep.h> #include <asm/offset.h>
@@ -74,7 +75,7 @@ current->counter =-100 ;while (1 ) { -while (!current->need_resched) { +while (!current->need_resched && !is_rcu_pending ()) { }schedule ();check_pgt_cache ();
arch/ppc/kernel/idle.c +2 -1
@@ -23,6 +23,7 @@#include <linux/unistd.h> #include <linux/ptrace.h> #include <linux/slab.h> +#include <linux/rcupdate.h> #include <asm/pgtable.h> #include <asm/uaccess.h>
@@ -74,7 +75,7 @@if (do_power_save && !current->need_resched)power_save (); -if (current->need_resched) { +if (current->need_resched ||is_rcu_pending ()) {schedule ();check_pgt_cache (); }
arch/s390/kernel/process.c +2 -1
@@ -36,6 +36,7 @@#include <linux/delay.h> #include <linux/reboot.h> #include <linux/init.h> +#include <linux/rcupdate.h> #include <asm/uaccess.h> #include <asm/pgtable.h>
@@ -63,7 +64,7 @@ wait_psw.mask = _WAIT_PSW_MASK; wait_psw.addr = (unsigned long ) &&idle_wakeup |0x80000000L ;while (1 ) { -if (current->need_resched) { +if (current->need_resched ||is_rcu_pending ()) {schedule ();check_pgt_cache ();continue ;
arch/s390x/kernel/process.c +2 -1
@@ -36,6 +36,7 @@#include <linux/delay.h> #include <linux/reboot.h> #include <linux/init.h> +#include <linux/rcupdate.h> #include <asm/uaccess.h> #include <asm/pgtable.h>
@@ -63,7 +64,7 @@ wait_psw.mask = _WAIT_PSW_MASK; wait_psw.addr = (unsigned long ) &&idle_wakeup;while (1 ) { -if (current->need_resched) { +if (current->need_resched ||is_rcu_pending ()) {schedule ();check_pgt_cache ();continue ;
arch/sh/kernel/process.c +2 -1
@@ -34,6 +34,7 @@#include <linux/reboot.h> #include <linux/init.h> #include <linux/irq.h> +#include <linux/rcupdate.h> #include <asm/uaccess.h> #include <asm/pgtable.h>
@@ -71,7 +72,7 @@ current->counter =-100 ;while (1 ) { -while (!current->need_resched) { +while (!current->need_resched && !is_rcu_pending ()) {if (hlt_counter)continue ;__sti ();
arch/sparc/kernel/process.c +2 -1
@@ -27,6 +27,7 @@#include <linux/smp_lock.h> #include <linux/reboot.h> #include <linux/delay.h> +#include <linux/rcupdate.h> #include <asm/auxio.h> #include <asm/oplib.h>
@@ -114,7 +115,7 @@init_idle ();while (1 ) { -if (current->need_resched) { +if (current->need_resched ||is_rcu_pending ()) {schedule ();check_pgt_cache (); }
arch/sparc64/kernel/process.c +2 -1
@@ -28,6 +28,7 @@#include <linux/config.h> #include <linux/reboot.h> #include <linux/delay.h> +#include <linux/rcupdate.h> #include <asm/oplib.h> #include <asm/uaccess.h>
@@ -88,7 +89,7 @@init_idle ();while (1 ) { -if (current->need_resched !=0 ) { +if (current->need_resched !=0 ||is_rcu_pending ()) {unidle_me ();schedule ();check_pgt_cache ();