ia64/xen-unstable

view xen/common/rcupdate.c @ 17062:0769835cf50f

x86 shadow: Reduce scope of shadow lock.

emulate_map_dest doesn't require holding lock, since
only shadow related operation possibly involved is to
remove shadow which is less frequent and can acquire
lock inside. Rest are either guest table walk or
per-vcpu monitor table manipulation

Signed-off-by Kevin Tian <kevin.tian@intel.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Feb 14 10:33:12 2008 +0000 (2008-02-14)
parents 759d924af6d8
children
line source
1 /*
2 * Read-Copy Update mechanism for mutual exclusion
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 *
18 * Copyright (C) IBM Corporation, 2001
19 *
20 * Authors: Dipankar Sarma <dipankar@in.ibm.com>
21 * Manfred Spraul <manfred@colorfullife.com>
22 *
23 * Modifications for Xen: Jose Renato Santos
24 * Copyright (C) Hewlett-Packard, 2006
25 *
26 * Based on the original work by Paul McKenney <paulmck@us.ibm.com>
27 * and inputs from Rusty Russell, Andrea Arcangeli and Andi Kleen.
28 * Papers:
29 * http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf
30 * http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf (OLS2001)
31 *
32 * For detailed explanation of Read-Copy Update mechanism see -
33 * http://lse.sourceforge.net/locking/rcupdate.html
34 */
35 #include <xen/types.h>
36 #include <xen/kernel.h>
37 #include <xen/init.h>
38 #include <xen/spinlock.h>
39 #include <xen/smp.h>
40 #include <xen/rcupdate.h>
41 #include <xen/sched.h>
42 #include <asm/atomic.h>
43 #include <xen/bitops.h>
44 #include <xen/percpu.h>
45 #include <xen/softirq.h>
47 /* Definition for rcupdate control block. */
48 struct rcu_ctrlblk rcu_ctrlblk = {
49 .cur = -300,
50 .completed = -300,
51 .lock = SPIN_LOCK_UNLOCKED,
52 .cpumask = CPU_MASK_NONE,
53 };
55 DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L };
57 static int blimit = 10;
58 static int qhimark = 10000;
59 static int qlowmark = 100;
60 static int rsinterval = 1000;
62 static void force_quiescent_state(struct rcu_data *rdp,
63 struct rcu_ctrlblk *rcp)
64 {
65 cpumask_t cpumask;
66 raise_softirq(SCHEDULE_SOFTIRQ);
67 if (unlikely(rdp->qlen - rdp->last_rs_qlen > rsinterval)) {
68 rdp->last_rs_qlen = rdp->qlen;
69 /*
70 * Don't send IPI to itself. With irqs disabled,
71 * rdp->cpu is the current cpu.
72 */
73 cpumask = rcp->cpumask;
74 cpu_clear(rdp->cpu, cpumask);
75 cpumask_raise_softirq(cpumask, SCHEDULE_SOFTIRQ);
76 }
77 }
79 /**
80 * call_rcu - Queue an RCU callback for invocation after a grace period.
81 * @head: structure to be used for queueing the RCU updates.
82 * @func: actual update function to be invoked after the grace period
83 *
84 * The update function will be invoked some time after a full grace
85 * period elapses, in other words after all currently executing RCU
86 * read-side critical sections have completed. RCU read-side critical
87 * sections are delimited by rcu_read_lock() and rcu_read_unlock(),
88 * and may be nested.
89 */
90 void fastcall call_rcu(struct rcu_head *head,
91 void (*func)(struct rcu_head *rcu))
92 {
93 unsigned long flags;
94 struct rcu_data *rdp;
96 head->func = func;
97 head->next = NULL;
98 local_irq_save(flags);
99 rdp = &__get_cpu_var(rcu_data);
100 *rdp->nxttail = head;
101 rdp->nxttail = &head->next;
102 if (unlikely(++rdp->qlen > qhimark)) {
103 rdp->blimit = INT_MAX;
104 force_quiescent_state(rdp, &rcu_ctrlblk);
105 }
106 local_irq_restore(flags);
107 }
109 /*
110 * Invoke the completed RCU callbacks. They are expected to be in
111 * a per-cpu list.
112 */
113 static void rcu_do_batch(struct rcu_data *rdp)
114 {
115 struct rcu_head *next, *list;
116 int count = 0;
118 list = rdp->donelist;
119 while (list) {
120 next = rdp->donelist = list->next;
121 list->func(list);
122 list = next;
123 rdp->qlen--;
124 if (++count >= rdp->blimit)
125 break;
126 }
127 if (rdp->blimit == INT_MAX && rdp->qlen <= qlowmark)
128 rdp->blimit = blimit;
129 if (!rdp->donelist)
130 rdp->donetail = &rdp->donelist;
131 else
132 raise_softirq(RCU_SOFTIRQ);
133 }
135 /*
136 * Grace period handling:
137 * The grace period handling consists out of two steps:
138 * - A new grace period is started.
139 * This is done by rcu_start_batch. The start is not broadcasted to
140 * all cpus, they must pick this up by comparing rcp->cur with
141 * rdp->quiescbatch. All cpus are recorded in the
142 * rcu_ctrlblk.cpumask bitmap.
143 * - All cpus must go through a quiescent state.
144 * Since the start of the grace period is not broadcasted, at least two
145 * calls to rcu_check_quiescent_state are required:
146 * The first call just notices that a new grace period is running. The
147 * following calls check if there was a quiescent state since the beginning
148 * of the grace period. If so, it updates rcu_ctrlblk.cpumask. If
149 * the bitmap is empty, then the grace period is completed.
150 * rcu_check_quiescent_state calls rcu_start_batch(0) to start the next grace
151 * period (if necessary).
152 */
153 /*
154 * Register a new batch of callbacks, and start it up if there is currently no
155 * active batch and the batch to be registered has not already occurred.
156 * Caller must hold rcu_ctrlblk.lock.
157 */
158 static void rcu_start_batch(struct rcu_ctrlblk *rcp)
159 {
160 if (rcp->next_pending &&
161 rcp->completed == rcp->cur) {
162 rcp->next_pending = 0;
163 /*
164 * next_pending == 0 must be visible in
165 * __rcu_process_callbacks() before it can see new value of cur.
166 */
167 smp_wmb();
168 rcp->cur++;
170 rcp->cpumask = cpu_online_map;
171 }
172 }
174 /*
175 * cpu went through a quiescent state since the beginning of the grace period.
176 * Clear it from the cpu mask and complete the grace period if it was the last
177 * cpu. Start another grace period if someone has further entries pending
178 */
179 static void cpu_quiet(int cpu, struct rcu_ctrlblk *rcp)
180 {
181 cpu_clear(cpu, rcp->cpumask);
182 if (cpus_empty(rcp->cpumask)) {
183 /* batch completed ! */
184 rcp->completed = rcp->cur;
185 rcu_start_batch(rcp);
186 }
187 }
189 /*
190 * Check if the cpu has gone through a quiescent state (say context
191 * switch). If so and if it already hasn't done so in this RCU
192 * quiescent cycle, then indicate that it has done so.
193 */
194 static void rcu_check_quiescent_state(struct rcu_ctrlblk *rcp,
195 struct rcu_data *rdp)
196 {
197 if (rdp->quiescbatch != rcp->cur) {
198 /* start new grace period: */
199 rdp->qs_pending = 1;
200 rdp->quiescbatch = rcp->cur;
201 return;
202 }
204 /* Grace period already completed for this cpu?
205 * qs_pending is checked instead of the actual bitmap to avoid
206 * cacheline trashing.
207 */
208 if (!rdp->qs_pending)
209 return;
211 rdp->qs_pending = 0;
213 spin_lock(&rcp->lock);
214 /*
215 * rdp->quiescbatch/rcp->cur and the cpu bitmap can come out of sync
216 * during cpu startup. Ignore the quiescent state.
217 */
218 if (likely(rdp->quiescbatch == rcp->cur))
219 cpu_quiet(rdp->cpu, rcp);
221 spin_unlock(&rcp->lock);
222 }
225 /*
226 * This does the RCU processing work from softirq context.
227 */
228 static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp,
229 struct rcu_data *rdp)
230 {
231 if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch)) {
232 *rdp->donetail = rdp->curlist;
233 rdp->donetail = rdp->curtail;
234 rdp->curlist = NULL;
235 rdp->curtail = &rdp->curlist;
236 }
238 local_irq_disable();
239 if (rdp->nxtlist && !rdp->curlist) {
240 rdp->curlist = rdp->nxtlist;
241 rdp->curtail = rdp->nxttail;
242 rdp->nxtlist = NULL;
243 rdp->nxttail = &rdp->nxtlist;
244 local_irq_enable();
246 /*
247 * start the next batch of callbacks
248 */
250 /* determine batch number */
251 rdp->batch = rcp->cur + 1;
252 /* see the comment and corresponding wmb() in
253 * the rcu_start_batch()
254 */
255 smp_rmb();
257 if (!rcp->next_pending) {
258 /* and start it/schedule start if it's a new batch */
259 spin_lock(&rcp->lock);
260 rcp->next_pending = 1;
261 rcu_start_batch(rcp);
262 spin_unlock(&rcp->lock);
263 }
264 } else {
265 local_irq_enable();
266 }
267 rcu_check_quiescent_state(rcp, rdp);
268 if (rdp->donelist)
269 rcu_do_batch(rdp);
270 }
272 static void rcu_process_callbacks(void)
273 {
274 __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data));
275 }
277 static int __rcu_pending(struct rcu_ctrlblk *rcp, struct rcu_data *rdp)
278 {
279 /* This cpu has pending rcu entries and the grace period
280 * for them has completed.
281 */
282 if (rdp->curlist && !rcu_batch_before(rcp->completed, rdp->batch))
283 return 1;
285 /* This cpu has no pending entries, but there are new entries */
286 if (!rdp->curlist && rdp->nxtlist)
287 return 1;
289 /* This cpu has finished callbacks to invoke */
290 if (rdp->donelist)
291 return 1;
293 /* The rcu core waits for a quiescent state from the cpu */
294 if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
295 return 1;
297 /* nothing to do */
298 return 0;
299 }
301 int rcu_pending(int cpu)
302 {
303 return __rcu_pending(&rcu_ctrlblk, &per_cpu(rcu_data, cpu));
304 }
306 /*
307 * Check to see if any future RCU-related work will need to be done
308 * by the current CPU, even if none need be done immediately, returning
309 * 1 if so. This function is part of the RCU implementation; it is -not-
310 * an exported member of the RCU API.
311 */
312 int rcu_needs_cpu(int cpu)
313 {
314 struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
316 return (!!rdp->curlist || rcu_pending(cpu));
317 }
319 void rcu_check_callbacks(int cpu)
320 {
321 raise_softirq(RCU_SOFTIRQ);
322 }
324 static void rcu_init_percpu_data(int cpu, struct rcu_ctrlblk *rcp,
325 struct rcu_data *rdp)
326 {
327 memset(rdp, 0, sizeof(*rdp));
328 rdp->curtail = &rdp->curlist;
329 rdp->nxttail = &rdp->nxtlist;
330 rdp->donetail = &rdp->donelist;
331 rdp->quiescbatch = rcp->completed;
332 rdp->qs_pending = 0;
333 rdp->cpu = cpu;
334 rdp->blimit = blimit;
335 }
337 void __devinit rcu_online_cpu(int cpu)
338 {
339 struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
341 rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp);
342 }
344 void __init rcu_init(void)
345 {
346 rcu_online_cpu(smp_processor_id());
347 open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
348 }