rcupreempt.c

Kernel code of linux kernel

		/*
		 * Since we can't determine the dynamic tick mode from
		 * the rcu_dyntick_sched.dynticks after this routine,
		 * we use a second flag to acknowledge that we came
		 * from an idle state with ticks stopped.
		 */
		per_cpu(rcu_update_flag, cpu)++;
		/*
		 * If we take an NMI/SMI now, they will also increment
		 * the rcu_update_flag, and will not update the
		 * rcu_dyntick_sched.dynticks on exit. That is for
		 * this IRQ to do.
		 */
	}
}

/**
 * rcu_irq_exit - Called from exiting Hard irq context.
 *
 * If the CPU was idle with dynamic ticks active, update the
 * rcu_dyntick_sched.dynticks to put let the RCU handling be
 * aware that the CPU is going back to idle with no ticks.
 */
void rcu_irq_exit(void)
{
	int cpu = smp_processor_id();
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	/*
	 * rcu_update_flag is set if we interrupted the CPU
	 * when it was idle with ticks stopped.
	 * Once this occurs, we keep track of interrupt nesting
	 * because a NMI/SMI could also come in, and we still
	 * only want the IRQ that started the increment of the
	 * rcu_dyntick_sched.dynticks to be the one that modifies
	 * it on exit.
	 */
	if (per_cpu(rcu_update_flag, cpu)) {
		if (--per_cpu(rcu_update_flag, cpu))
			return;

		/* This must match the interrupt nesting */
		WARN_ON(in_interrupt());

		/*
		 * If an NMI/SMI happens now we are still
		 * protected by the rcu_dyntick_sched.dynticks being odd.
		 */

		/*
		 * The following memory barrier ensures that any
		 * rcu_read_unlock() primitives in the irq handler
		 * are seen by other CPUs to preceed the following
		 * increment to rcu_dyntick_sched.dynticks. This
		 * is required in order for other CPUs to determine
		 * when it is safe to advance the RCU grace-period
		 * state machine.
		 */
		smp_mb(); /* see above block comment. */
		rdssp->dynticks++;
		WARN_ON(rdssp->dynticks & 0x1);
	}
}

static void dyntick_save_progress_counter(int cpu)
{
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	rdssp->dynticks_snap = rdssp->dynticks;
}

static inline int
rcu_try_flip_waitack_needed(int cpu)
{
	long curr;
	long snap;
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	curr = rdssp->dynticks;
	snap = rdssp->dynticks_snap;
	smp_mb(); /* force ordering with cpu entering/leaving dynticks. */

	/*
	 * If the CPU remained in dynticks mode for the entire time
	 * and didn't take any interrupts, NMIs, SMIs, or whatever,
	 * then it cannot be in the middle of an rcu_read_lock(), so
	 * the next rcu_read_lock() it executes must use the new value
	 * of the counter.  So we can safely pretend that this CPU
	 * already acknowledged the counter.
	 */

	if ((curr == snap) && ((curr & 0x1) == 0))
		return 0;

	/*
	 * If the CPU passed through or entered a dynticks idle phase with
	 * no active irq handlers, then, as above, we can safely pretend
	 * that this CPU already acknowledged the counter.
	 */

	if ((curr - snap) > 2 || (curr & 0x1) == 0)
		return 0;

	/* We need this CPU to explicitly acknowledge the counter flip. */

	return 1;
}

static inline int
rcu_try_flip_waitmb_needed(int cpu)
{
	long curr;
	long snap;
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	curr = rdssp->dynticks;
	snap = rdssp->dynticks_snap;
	smp_mb(); /* force ordering with cpu entering/leaving dynticks. */

	/*
	 * If the CPU remained in dynticks mode for the entire time
	 * and didn't take any interrupts, NMIs, SMIs, or whatever,
	 * then it cannot have executed an RCU read-side critical section
	 * during that time, so there is no need for it to execute a
	 * memory barrier.
	 */

	if ((curr == snap) && ((curr & 0x1) == 0))
		return 0;

	/*
	 * If the CPU either entered or exited an outermost interrupt,
	 * SMI, NMI, or whatever handler, then we know that it executed
	 * a memory barrier when doing so.  So we don't need another one.
	 */
	if (curr != snap)
		return 0;

	/* We need the CPU to execute a memory barrier. */

	return 1;
}

static void dyntick_save_progress_counter_sched(int cpu)
{
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	rdssp->sched_dynticks_snap = rdssp->dynticks;
}

static int rcu_qsctr_inc_needed_dyntick(int cpu)
{
	long curr;
	long snap;
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	curr = rdssp->dynticks;
	snap = rdssp->sched_dynticks_snap;
	smp_mb(); /* force ordering with cpu entering/leaving dynticks. */

	/*
	 * If the CPU remained in dynticks mode for the entire time
	 * and didn't take any interrupts, NMIs, SMIs, or whatever,
	 * then it cannot be in the middle of an rcu_read_lock(), so
	 * the next rcu_read_lock() it executes must use the new value
	 * of the counter.  Therefore, this CPU has been in a quiescent
	 * state the entire time, and we don't need to wait for it.
	 */

	if ((curr == snap) && ((curr & 0x1) == 0))
		return 0;

	/*
	 * If the CPU passed through or entered a dynticks idle phase with
	 * no active irq handlers, then, as above, this CPU has already
	 * passed through a quiescent state.
	 */

	if ((curr - snap) > 2 || (snap & 0x1) == 0)
		return 0;

	/* We need this CPU to go through a quiescent state. */

	return 1;
}

#else /* !CONFIG_NO_HZ */

# define dyntick_save_progress_counter(cpu)		do { } while (0)
# define rcu_try_flip_waitack_needed(cpu)		(1)
# define rcu_try_flip_waitmb_needed(cpu)		(1)

# define dyntick_save_progress_counter_sched(cpu)	do { } while (0)
# define rcu_qsctr_inc_needed_dyntick(cpu)		(1)

#endif /* CONFIG_NO_HZ */

static void save_qsctr_sched(int cpu)
{
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	rdssp->sched_qs_snap = rdssp->sched_qs;
}

static inline int rcu_qsctr_inc_needed(int cpu)
{
	struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);

	/*
	 * If there has been a quiescent state, no more need to wait
	 * on this CPU.
	 */

	if (rdssp->sched_qs != rdssp->sched_qs_snap) {
		smp_mb(); /* force ordering with cpu entering schedule(). */
		return 0;
	}

	/* We need this CPU to go through a quiescent state. */

	return 1;
}

/*
 * Get here when RCU is idle.  Decide whether we need to
 * move out of idle state, and return non-zero if so.
 * "Straightforward" approach for the moment, might later
 * use callback-list lengths, grace-period duration, or
 * some such to determine when to exit idle state.
 * Might also need a pre-idle test that does not acquire
 * the lock, but let's get the simple case working first...
 */

static int
rcu_try_flip_idle(void)
{
	int cpu;

	RCU_TRACE_ME(rcupreempt_trace_try_flip_i1);
	if (!rcu_pending(smp_processor_id())) {
		RCU_TRACE_ME(rcupreempt_trace_try_flip_ie1);
		return 0;
	}

	/*
	 * Do the flip.
	 */

	RCU_TRACE_ME(rcupreempt_trace_try_flip_g1);
	rcu_ctrlblk.completed++;  /* stands in for rcu_try_flip_g2 */

	/*
	 * Need a memory barrier so that other CPUs see the new
	 * counter value before they see the subsequent change of all
	 * the rcu_flip_flag instances to rcu_flipped.
	 */

	smp_mb();	/* see above block comment. */

	/* Now ask each CPU for acknowledgement of the flip. */

	for_each_cpu_mask_nr(cpu, rcu_cpu_online_map) {
		per_cpu(rcu_flip_flag, cpu) = rcu_flipped;
		dyntick_save_progress_counter(cpu);
	}

	return 1;
}

/*
 * Wait for CPUs to acknowledge the flip.
 */

static int
rcu_try_flip_waitack(void)
{
	int cpu;

	RCU_TRACE_ME(rcupreempt_trace_try_flip_a1);
	for_each_cpu_mask_nr(cpu, rcu_cpu_online_map)
		if (rcu_try_flip_waitack_needed(cpu) &&
		    per_cpu(rcu_flip_flag, cpu) != rcu_flip_seen) {
			RCU_TRACE_ME(rcupreempt_trace_try_flip_ae1);
			return 0;
		}

	/*
	 * Make sure our checks above don't bleed into subsequent
	 * waiting for the sum of the counters to reach zero.
	 */

	smp_mb();	/* see above block comment. */
	RCU_TRACE_ME(rcupreempt_trace_try_flip_a2);
	return 1;
}

/*
 * Wait for collective ``last'' counter to reach zero,
 * then tell all CPUs to do an end-of-grace-period memory barrier.
 */

static int
rcu_try_flip_waitzero(void)
{
	int cpu;
	int lastidx = !(rcu_ctrlblk.completed & 0x1);
	int sum = 0;

	/* Check to see if the sum of the "last" counters is zero. */

	RCU_TRACE_ME(rcupreempt_trace_try_flip_z1);
	for_each_cpu_mask_nr(cpu, rcu_cpu_online_map)
		sum += RCU_DATA_CPU(cpu)->rcu_flipctr[lastidx];
	if (sum != 0) {
		RCU_TRACE_ME(rcupreempt_trace_try_flip_ze1);
		return 0;
	}

	/*
	 * This ensures that the other CPUs see the call for
	 * memory barriers -after- the sum to zero has been
	 * detected here
	 */
	smp_mb();  /*  ^^^^^^^^^^^^ */

	/* Call for a memory barrier from each CPU. */
	for_each_cpu_mask_nr(cpu, rcu_cpu_online_map) {
		per_cpu(rcu_mb_flag, cpu) = rcu_mb_needed;
		dyntick_save_progress_counter(cpu);
	}

	RCU_TRACE_ME(rcupreempt_trace_try_flip_z2);
	return 1;
}

/*
 * Wait for all CPUs to do their end-of-grace-period memory barrier.
 * Return 0 once all CPUs have done so.
 */

static int
rcu_try_flip_waitmb(void)
{
	int cpu;

	RCU_TRACE_ME(rcupreempt_trace_try_flip_m1);
	for_each_cpu_mask_nr(cpu, rcu_cpu_online_map)
		if (rcu_try_flip_waitmb_needed(cpu) &&
		    per_cpu(rcu_mb_flag, cpu) != rcu_mb_done) {
			RCU_TRACE_ME(rcupreempt_trace_try_flip_me1);
			return 0;
		}

	smp_mb(); /* Ensure that the above checks precede any following flip. */
	RCU_TRACE_ME(rcupreempt_trace_try_flip_m2);
	return 1;
}

/*
 * Attempt a single flip of the counters.  Remember, a single flip does
 * -not- constitute a grace period.  Instead, the interval between
 * at least GP_STAGES consecutive flips is a grace period.
 *
 * If anyone is nuts enough to run this CONFIG_PREEMPT_RCU implementation
 * on a large SMP, they might want to use a hierarchical organization of
 * the per-CPU-counter pairs.
 */
static void rcu_try_flip(void)
{
	unsigned long flags;

	RCU_TRACE_ME(rcupreempt_trace_try_flip_1);
	if (unlikely(!spin_trylock_irqsave(&rcu_ctrlblk.fliplock, flags))) {
		RCU_TRACE_ME(rcupreempt_trace_try_flip_e1);
		return;
	}

	/*
	 * Take the next transition(s) through the RCU grace-period
	 * flip-counter state machine.
	 */

	switch (rcu_ctrlblk.rcu_try_flip_state) {
	case rcu_try_flip_idle_state:
		if (rcu_try_flip_idle())
			rcu_ctrlblk.rcu_try_flip_state =
				rcu_try_flip_waitack_state;
		break;
	case rcu_try_flip_waitack_state:
		if (rcu_try_flip_waitack())
			rcu_ctrlblk.rcu_try_flip_state =
				rcu_try_flip_waitzero_state;
		break;
	case rcu_try_flip_waitzero_state:
		if (rcu_try_flip_waitzero())
			rcu_ctrlblk.rcu_try_flip_state =
				rcu_try_flip_waitmb_state;
		break;
	case rcu_try_flip_waitmb_state:
		if (rcu_try_flip_waitmb())
			rcu_ctrlblk.rcu_try_flip_state =
				rcu_try_flip_idle_state;
	}
	spin_unlock_irqrestore(&rcu_ctrlblk.fliplock, flags);
}

/*
 * Check to see if this CPU needs to do a memory barrier in order to
 * ensure that any prior RCU read-side critical sections have committed
 * their counter manipulations and critical-section memory references
 * before declaring the grace period to be completed.
 */
static void rcu_check_mb(int cpu)
{
	if (per_cpu(rcu_mb_flag, cpu) == rcu_mb_needed) {
		smp_mb();  /* Ensure RCU read-side accesses are visible. */
		per_cpu(rcu_mb_flag, cpu) = rcu_mb_done;
	}
}

void rcu_check_callbacks(int cpu, int user)
{
	unsigned long flags;
	struct rcu_data *rdp = RCU_DATA_CPU(cpu);

	/*
	 * If this CPU took its interrupt from user mode or from the
	 * idle loop, and this is not a nested interrupt, then
	 * this CPU has to have exited all prior preept-disable
	 * sections of code.  So increment the counter to note this.
	 *
	 * The memory barrier is needed to handle the case where
	 * writes from a preempt-disable section of code get reordered
	 * into schedule() by this CPU's write buffer.  So the memory
	 * barrier makes sure that the rcu_qsctr_inc() is seen by other
	 * CPUs to happen after any such write.
	 */

	if (user ||
	    (idle_cpu(cpu) && !in_softirq() &&
	     hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
		smp_mb();	/* Guard against aggressive schedule(). */
	     	rcu_qsctr_inc(cpu);
	}

	rcu_check_mb(cpu);
	if (rcu_ctrlblk.completed == rdp->completed)
		rcu_try_flip();
	spin_lock_irqsave(&rdp->lock, flags);
	RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp);
	__rcu_advance_callbacks(rdp);
	if (rdp->donelist == NULL) {
		spin_unlock_irqrestore(&rdp->lock, flags);
	} else {
		spin_unlock_irqrestore(&rdp->lock, flags);
		raise_softirq(RCU_SOFTIRQ);
	}
}

/*
 * Needed by dynticks, to make sure all RCU processing has finished
 * when we go idle:
 */
void rcu_advance_callbacks(int cpu, int user)
{
	unsigned long flags;
	struct rcu_data *rdp = RCU_DATA_CPU(cpu);

	if (rcu_ctrlblk.completed == rdp->completed) {
		rcu_try_flip();
		if (rcu_ctrlblk.completed == rdp->completed)
			return;
	}
	spin_lock_irqsave(&rdp->lock, flags);
	RCU_TRACE_RDP(rcupreempt_trace_check_callbacks, rdp);
	__rcu_advance_callbacks(rdp);
	spin_unlock_irqrestore(&rdp->lock, flags);
}

#ifdef CONFIG_HOTPLUG_CPU
#define rcu_offline_cpu_enqueue(srclist, srctail, dstlist, dsttail) do { \
		*dsttail = srclist; \
		if (srclist != NULL) { \
			dsttail = srctail; \
			srclist = NULL; \
			srctail = &srclist;\
		} \
	} while (0)

void rcu_offline_cpu(int cpu)
{
	int i;
	struct rcu_head *list = NULL;
	unsigned long flags;
	struct rcu_data *rdp = RCU_DATA_CPU(cpu);
	struct rcu_head *schedlist = NULL;
	struct rcu_head **schedtail = &schedlist;