X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;ds=sidebyside;f=kernel%2Frcupdate.c;h=1b16bfc7d1eea593b8499e6942aa2464da485de1;hb=c7b5ebbddf7bcd3651947760f423e3783bbe6573;hp=f9324b7c8c1025fd3c695e96f771280d66d75d0a;hpb=5273a3df6485dc2ad6aa7ddd441b9a21970f003b;p=linux-2.6.git diff --git a/kernel/rcupdate.c b/kernel/rcupdate.c index f9324b7c8..1b16bfc7d 100644 --- a/kernel/rcupdate.c +++ b/kernel/rcupdate.c @@ -17,9 +17,10 @@ * * Copyright (C) IBM Corporation, 2001 * - * Author: Dipankar Sarma + * Authors: Dipankar Sarma + * Manfred Spraul * - * Based on the original work by Paul McKenney + * Based on the original work by Paul McKenney * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen. * Papers: * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf @@ -40,6 +41,7 @@ #include #include #include +#include #include #include #include @@ -47,35 +49,83 @@ /* Definition for rcupdate control block. */ struct rcu_ctrlblk rcu_ctrlblk = - { .mutex = SPIN_LOCK_UNLOCKED, .curbatch = 1, - .maxbatch = 1, .rcu_cpu_mask = CPU_MASK_NONE }; + { .cur = -300, .completed = -300 , .lock = SEQCNT_ZERO }; +struct rcu_ctrlblk rcu_bh_ctrlblk = + { .cur = -300, .completed = -300 , .lock = SEQCNT_ZERO }; + +/* Bookkeeping of the progress of the grace period */ +struct rcu_state { + spinlock_t lock; /* Guard this struct and writes to rcu_ctrlblk */ + cpumask_t cpumask; /* CPUs that need to switch in order */ + /* for current batch to proceed. */ +}; + +struct rcu_state rcu_state ____cacheline_maxaligned_in_smp = + {.lock = SPIN_LOCK_UNLOCKED, .cpumask = CPU_MASK_NONE }; +struct rcu_state rcu_bh_state ____cacheline_maxaligned_in_smp = + {.lock = SPIN_LOCK_UNLOCKED, .cpumask = CPU_MASK_NONE }; + DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L }; +DEFINE_PER_CPU(struct rcu_data, rcu_bh_data) = { 0L }; /* Fake initialization required by compiler */ static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL}; -#define RCU_tasklet(cpu) (per_cpu(rcu_tasklet, cpu)) +static int maxbatch = 10; + +/** + * call_rcu - Queue an RCU callback for invocation after a grace period. + * @head: structure to be used for queueing the RCU updates. + * @func: actual update function to be invoked after the grace period + * + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. RCU read-side critical + * sections are delimited by rcu_read_lock() and rcu_read_unlock(), + * and may be nested. + */ +void fastcall call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) +{ + unsigned long flags; + struct rcu_data *rdp; + + head->func = func; + head->next = NULL; + local_irq_save(flags); + rdp = &__get_cpu_var(rcu_data); + *rdp->nxttail = head; + rdp->nxttail = &head->next; + local_irq_restore(flags); +} /** - * call_rcu - Queue an RCU update request. + * call_rcu_bh - Queue an RCU for invocation after a quicker grace period. * @head: structure to be used for queueing the RCU updates. * @func: actual update function to be invoked after the grace period - * @arg: argument to be passed to the update function * - * The update function will be invoked as soon as all CPUs have performed - * a context switch or been seen in the idle loop or in a user process. - * The read-side of critical section that use call_rcu() for updation must - * be protected by rcu_read_lock()/rcu_read_unlock(). + * The update function will be invoked some time after a full grace + * period elapses, in other words after all currently executing RCU + * read-side critical sections have completed. call_rcu_bh() assumes + * that the read-side critical sections end on completion of a softirq + * handler. This means that read-side critical sections in process + * context must not be interrupted by softirqs. This interface is to be + * used when most of the read-side critical sections are in softirq context. + * RCU read-side critical sections are delimited by rcu_read_lock() and + * rcu_read_unlock(), * if in interrupt context or rcu_read_lock_bh() + * and rcu_read_unlock_bh(), if in process context. These may be nested. */ -void fastcall call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg) +void fastcall call_rcu_bh(struct rcu_head *head, + void (*func)(struct rcu_head *rcu)) { - int cpu; unsigned long flags; + struct rcu_data *rdp; head->func = func; - head->arg = arg; + head->next = NULL; local_irq_save(flags); - cpu = smp_processor_id(); - list_add_tail(&head->list, &RCU_nxtlist(cpu)); + rdp = &__get_cpu_var(rcu_bh_data); + *rdp->nxttail = head; + rdp->nxttail = &head->next; local_irq_restore(flags); } @@ -83,39 +133,78 @@ void fastcall call_rcu(struct rcu_head *head, void (*func)(void *arg), void *arg * Invoke the completed RCU callbacks. They are expected to be in * a per-cpu list. */ -static void rcu_do_batch(struct list_head *list) +static void rcu_do_batch(struct rcu_data *rdp) { - struct list_head *entry; - struct rcu_head *head; - - while (!list_empty(list)) { - entry = list->next; - list_del(entry); - head = list_entry(entry, struct rcu_head, list); - head->func(head->arg); + struct rcu_head *next, *list; + int count = 0; + + list = rdp->donelist; + while (list) { + next = rdp->donelist = list->next; + list->func(list); + list = next; + if (++count >= maxbatch) + break; } + if (!rdp->donelist) + rdp->donetail = &rdp->donelist; + else + tasklet_schedule(&per_cpu(rcu_tasklet, rdp->cpu)); } +/* + * Grace period handling: + * The grace period handling consists out of two steps: + * - A new grace period is started. + * This is done by rcu_start_batch. The start is not broadcasted to + * all cpus, they must pick this up by comparing rcp->cur with + * rdp->quiescbatch. All cpus are recorded in the + * rcu_state.cpumask bitmap. + * - All cpus must go through a quiescent state. + * Since the start of the grace period is not broadcasted, at least two + * calls to rcu_check_quiescent_state are required: + * The first call just notices that a new grace period is running. The + * following calls check if there was a quiescent state since the beginning + * of the grace period. If so, it updates rcu_state.cpumask. If + * the bitmap is empty, then the grace period is completed. + * rcu_check_quiescent_state calls rcu_start_batch(0) to start the next grace + * period (if necessary). + */ /* * Register a new batch of callbacks, and start it up if there is currently no * active batch and the batch to be registered has not already occurred. - * Caller must hold the rcu_ctrlblk lock. + * Caller must hold rcu_state.lock. */ -static void rcu_start_batch(long newbatch) +static void rcu_start_batch(struct rcu_ctrlblk *rcp, struct rcu_state *rsp, + int next_pending) { - cpumask_t active; - - if (rcu_batch_before(rcu_ctrlblk.maxbatch, newbatch)) { - rcu_ctrlblk.maxbatch = newbatch; + if (next_pending) + rcp->next_pending = 1; + + if (rcp->next_pending && + rcp->completed == rcp->cur) { + /* Can't change, since spin lock held. */ + cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask); + write_seqcount_begin(&rcp->lock); + rcp->next_pending = 0; + rcp->cur++; + write_seqcount_end(&rcp->lock); } - if (rcu_batch_before(rcu_ctrlblk.maxbatch, rcu_ctrlblk.curbatch) || - !cpus_empty(rcu_ctrlblk.rcu_cpu_mask)) { - return; +} + +/* + * cpu went through a quiescent state since the beginning of the grace period. + * Clear it from the cpu mask and complete the grace period if it was the last + * cpu. Start another grace period if someone has further entries pending + */ +static void cpu_quiet(int cpu, struct rcu_ctrlblk *rcp, struct rcu_state *rsp) +{ + cpu_clear(cpu, rsp->cpumask); + if (cpus_empty(rsp->cpumask)) { + /* batch completed ! */ + rcp->completed = rcp->cur; + rcu_start_batch(rcp, rsp, 0); } - /* Can't change, since spin lock held. */ - active = idle_cpu_mask; - cpus_complement(active); - cpus_and(rcu_ctrlblk.rcu_cpu_mask, cpu_online_map, active); } /* @@ -123,11 +212,22 @@ static void rcu_start_batch(long newbatch) * switch). If so and if it already hasn't done so in this RCU * quiescent cycle, then indicate that it has done so. */ -static void rcu_check_quiescent_state(void) +static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp, + struct rcu_state *rsp, struct rcu_data *rdp) { - int cpu = smp_processor_id(); + if (rdp->quiescbatch != rcp->cur) { + /* new grace period: record qsctr value. */ + rdp->qs_pending = 1; + rdp->last_qsctr = rdp->qsctr; + rdp->quiescbatch = rcp->cur; + return; + } - if (!cpu_isset(cpu, rcu_ctrlblk.rcu_cpu_mask)) + /* Grace period already completed for this cpu? + * qs_pending is checked instead of the actual bitmap to avoid + * cacheline trashing. + */ + if (!rdp->qs_pending) return; /* @@ -135,27 +235,19 @@ static void rcu_check_quiescent_state(void) * we may miss one quiescent state of that CPU. That is * tolerable. So no need to disable interrupts. */ - if (RCU_last_qsctr(cpu) == RCU_QSCTR_INVALID) { - RCU_last_qsctr(cpu) = RCU_qsctr(cpu); + if (rdp->qsctr == rdp->last_qsctr) return; - } - if (RCU_qsctr(cpu) == RCU_last_qsctr(cpu)) - return; - - spin_lock(&rcu_ctrlblk.mutex); - if (!cpu_isset(cpu, rcu_ctrlblk.rcu_cpu_mask)) - goto out_unlock; + rdp->qs_pending = 0; - cpu_clear(cpu, rcu_ctrlblk.rcu_cpu_mask); - RCU_last_qsctr(cpu) = RCU_QSCTR_INVALID; - if (!cpus_empty(rcu_ctrlblk.rcu_cpu_mask)) - goto out_unlock; - - rcu_ctrlblk.curbatch++; - rcu_start_batch(rcu_ctrlblk.maxbatch); + spin_lock(&rsp->lock); + /* + * rdp->quiescbatch/rcp->cur and the cpu bitmap can come out of sync + * during cpu startup. Ignore the quiescent state. + */ + if (likely(rdp->quiescbatch == rcp->cur)) + cpu_quiet(rdp->cpu, rcp, rsp); -out_unlock: - spin_unlock(&rcu_ctrlblk.mutex); + spin_unlock(&rsp->lock); } @@ -165,50 +257,49 @@ out_unlock: * locking requirements, the list it's pulling from has to belong to a cpu * which is dead and hence not processing interrupts. */ -static void rcu_move_batch(struct list_head *list) +static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list, + struct rcu_head **tail) { - struct list_head *entry; - int cpu = smp_processor_id(); - local_irq_disable(); - while (!list_empty(list)) { - entry = list->next; - list_del(entry); - list_add_tail(entry, &RCU_nxtlist(cpu)); - } + *this_rdp->nxttail = list; + if (list) + this_rdp->nxttail = tail; local_irq_enable(); } -static void rcu_offline_cpu(int cpu) +static void __rcu_offline_cpu(struct rcu_data *this_rdp, + struct rcu_ctrlblk *rcp, struct rcu_state *rsp, struct rcu_data *rdp) { /* if the cpu going offline owns the grace period * we can block indefinitely waiting for it, so flush * it here */ - spin_lock_irq(&rcu_ctrlblk.mutex); - if (cpus_empty(rcu_ctrlblk.rcu_cpu_mask)) - goto unlock; - - cpu_clear(cpu, rcu_ctrlblk.rcu_cpu_mask); - if (cpus_empty(rcu_ctrlblk.rcu_cpu_mask)) { - rcu_ctrlblk.curbatch++; - /* We may avoid calling start batch if - * we are starting the batch only - * because of the DEAD CPU (the current - * CPU will start a new batch anyway for - * the callbacks we will move to current CPU). - * However, we will avoid this optimisation - * for now. - */ - rcu_start_batch(rcu_ctrlblk.maxbatch); - } -unlock: - spin_unlock_irq(&rcu_ctrlblk.mutex); + spin_lock_bh(&rsp->lock); + if (rcp->cur != rcp->completed) + cpu_quiet(rdp->cpu, rcp, rsp); + spin_unlock_bh(&rsp->lock); + rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail); + rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail); + +} +static void rcu_offline_cpu(int cpu) +{ + struct rcu_data *this_rdp = &get_cpu_var(rcu_data); + struct rcu_data *this_bh_rdp = &get_cpu_var(rcu_bh_data); + + __rcu_offline_cpu(this_rdp, &rcu_ctrlblk, &rcu_state, + &per_cpu(rcu_data, cpu)); + __rcu_offline_cpu(this_bh_rdp, &rcu_bh_ctrlblk, &rcu_bh_state, + &per_cpu(rcu_bh_data, cpu)); + put_cpu_var(rcu_data); + put_cpu_var(rcu_bh_data); + tasklet_kill_immediate(&per_cpu(rcu_tasklet, cpu), cpu); +} - rcu_move_batch(&RCU_curlist(cpu)); - rcu_move_batch(&RCU_nxtlist(cpu)); +#else - tasklet_kill_immediate(&RCU_tasklet(cpu), cpu); +static void rcu_offline_cpu(int cpu) +{ } #endif @@ -216,53 +307,90 @@ unlock: /* * This does the RCU processing work from tasklet context. */ -static void rcu_process_callbacks(unsigned long unused) +static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp, + struct rcu_state *rsp, struct rcu_data *rdp) { - int cpu = smp_processor_id(); - LIST_HEAD(list); - - if (!list_empty(&RCU_curlist(cpu)) && - rcu_batch_after(rcu_ctrlblk.curbatch, RCU_batch(cpu))) { - list_splice(&RCU_curlist(cpu), &list); - INIT_LIST_HEAD(&RCU_curlist(cpu)); + if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) { + *rdp->donetail = rdp->curlist; + rdp->donetail = rdp->curtail; + rdp->curlist = NULL; + rdp->curtail = &rdp->curlist; } local_irq_disable(); - if (!list_empty(&RCU_nxtlist(cpu)) && list_empty(&RCU_curlist(cpu))) { - list_splice(&RCU_nxtlist(cpu), &RCU_curlist(cpu)); - INIT_LIST_HEAD(&RCU_nxtlist(cpu)); + if (rdp->nxtlist && !rdp->curlist) { + int next_pending, seq; + + rdp->curlist = rdp->nxtlist; + rdp->curtail = rdp->nxttail; + rdp->nxtlist = NULL; + rdp->nxttail = &rdp->nxtlist; local_irq_enable(); /* * start the next batch of callbacks */ - spin_lock(&rcu_ctrlblk.mutex); - RCU_batch(cpu) = rcu_ctrlblk.curbatch + 1; - rcu_start_batch(RCU_batch(cpu)); - spin_unlock(&rcu_ctrlblk.mutex); + do { + seq = read_seqcount_begin(&rcp->lock); + /* determine batch number */ + rdp->batch = rcp->cur + 1; + next_pending = rcp->next_pending; + } while (read_seqcount_retry(&rcp->lock, seq)); + + if (!next_pending) { + /* and start it/schedule start if it's a new batch */ + spin_lock(&rsp->lock); + rcu_start_batch(rcp, rsp, 1); + spin_unlock(&rsp->lock); + } } else { local_irq_enable(); } - rcu_check_quiescent_state(); - if (!list_empty(&list)) - rcu_do_batch(&list); + rcu_check_quiescent_state(rcp, rsp, rdp); + if (rdp->donelist) + rcu_do_batch(rdp); +} + +static void rcu_process_callbacks(unsigned long unused) +{ + __rcu_process_callbacks(&rcu_ctrlblk, &rcu_state, + &__get_cpu_var(rcu_data)); + __rcu_process_callbacks(&rcu_bh_ctrlblk, &rcu_bh_state, + &__get_cpu_var(rcu_bh_data)); } void rcu_check_callbacks(int cpu, int user) { if (user || (idle_cpu(cpu) && !in_softirq() && - hardirq_count() <= (1 << HARDIRQ_SHIFT))) - RCU_qsctr(cpu)++; - tasklet_schedule(&RCU_tasklet(cpu)); + hardirq_count() <= (1 << HARDIRQ_SHIFT))) { + rcu_qsctr_inc(cpu); + rcu_bh_qsctr_inc(cpu); + } else if (!in_softirq()) + rcu_bh_qsctr_inc(cpu); + tasklet_schedule(&per_cpu(rcu_tasklet, cpu)); +} + +static void rcu_init_percpu_data(int cpu, struct rcu_ctrlblk *rcp, + struct rcu_data *rdp) +{ + memset(rdp, 0, sizeof(*rdp)); + rdp->curtail = &rdp->curlist; + rdp->nxttail = &rdp->nxtlist; + rdp->donetail = &rdp->donelist; + rdp->quiescbatch = rcp->completed; + rdp->qs_pending = 0; + rdp->cpu = cpu; } static void __devinit rcu_online_cpu(int cpu) { - memset(&per_cpu(rcu_data, cpu), 0, sizeof(struct rcu_data)); - tasklet_init(&RCU_tasklet(cpu), rcu_process_callbacks, 0UL); - INIT_LIST_HEAD(&RCU_nxtlist(cpu)); - INIT_LIST_HEAD(&RCU_curlist(cpu)); + struct rcu_data *rdp = &per_cpu(rcu_data, cpu); + struct rcu_data *bh_rdp = &per_cpu(rcu_bh_data, cpu); + + rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp); + rcu_init_percpu_data(cpu, &rcu_bh_ctrlblk, bh_rdp); + tasklet_init(&per_cpu(rcu_tasklet, cpu), rcu_process_callbacks, 0UL); } static int __devinit rcu_cpu_notify(struct notifier_block *self, @@ -273,11 +401,9 @@ static int __devinit rcu_cpu_notify(struct notifier_block *self, case CPU_UP_PREPARE: rcu_online_cpu(cpu); break; -#ifdef CONFIG_HOTPLUG_CPU case CPU_DEAD: rcu_offline_cpu(cpu); break; -#endif default: break; } @@ -302,29 +428,42 @@ void __init rcu_init(void) register_cpu_notifier(&rcu_nb); } +struct rcu_synchronize { + struct rcu_head head; + struct completion completion; +}; /* Because of FASTCALL declaration of complete, we use this wrapper */ -static void wakeme_after_rcu(void *completion) +static void wakeme_after_rcu(struct rcu_head *head) { - complete(completion); + struct rcu_synchronize *rcu; + + rcu = container_of(head, struct rcu_synchronize, head); + complete(&rcu->completion); } /** - * synchronize-kernel - wait until all the CPUs have gone - * through a "quiescent" state. It may sleep. + * synchronize_kernel - wait until a grace period has elapsed. + * + * Control will return to the caller some time after a full grace + * period has elapsed, in other words after all currently executing RCU + * read-side critical sections have completed. RCU read-side critical + * sections are delimited by rcu_read_lock() and rcu_read_unlock(), + * and may be nested. */ void synchronize_kernel(void) { - struct rcu_head rcu; - DECLARE_COMPLETION(completion); + struct rcu_synchronize rcu; + init_completion(&rcu.completion); /* Will wake me after RCU finished */ - call_rcu(&rcu, wakeme_after_rcu, &completion); + call_rcu(&rcu.head, wakeme_after_rcu); /* Wait for it */ - wait_for_completion(&completion); + wait_for_completion(&rcu.completion); } - +module_param(maxbatch, int, 0); EXPORT_SYMBOL(call_rcu); +EXPORT_SYMBOL(call_rcu_bh); EXPORT_SYMBOL(synchronize_kernel);