← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xen/utopic

« back to all changes in this revision

Viewing changes to xen/common/rcupdate.c

  • Committer: Bazaar Package Importer
  • Author(s): Bastian Blank
  • Date: 2010-05-06 15:47:38 UTC
  • mto: (1.3.1) (15.1.1 sid) (4.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20100506154738-agoz0rlafrh1fnq7
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
xen/common/rcupdate.c
 
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>
 
46
 
 
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
};
 
54
 
 
55
DEFINE_PER_CPU(struct rcu_data, rcu_data) = { 0L };
 
56
 
 
57
static int blimit = 10;
 
58
static int qhimark = 10000;
 
59
static int qlowmark = 100;
 
60
static int rsinterval = 1000;
 
61
 
 
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
}
 
78
 
 
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;
 
95
 
 
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
}
 
108
 
 
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;
 
117
 
 
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
}
 
134
 
 
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++;
 
169
 
 
170
        rcp->cpumask = cpu_online_map;
 
171
    }
 
172
}
 
173
 
 
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
}
 
188
 
 
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
    }
 
203
 
 
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;
 
210
 
 
211
    rdp->qs_pending = 0;
 
212
 
 
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);
 
220
 
 
221
    spin_unlock(&rcp->lock);
 
222
}
 
223
 
 
224
 
 
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
    }
 
237
 
 
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();
 
245
 
 
246
        /*
 
247
         * start the next batch of callbacks
 
248
         */
 
249
 
 
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();
 
256
 
 
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
}
 
271
 
 
272
static void rcu_process_callbacks(void)
 
273
{
 
274
    __rcu_process_callbacks(&rcu_ctrlblk, &__get_cpu_var(rcu_data));
 
275
}
 
276
 
 
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;
 
284
 
 
285
    /* This cpu has no pending entries, but there are new entries */
 
286
    if (!rdp->curlist && rdp->nxtlist)
 
287
        return 1;
 
288
 
 
289
    /* This cpu has finished callbacks to invoke */
 
290
    if (rdp->donelist)
 
291
        return 1;
 
292
 
 
293
    /* The rcu core waits for a quiescent state from the cpu */
 
294
    if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
 
295
        return 1;
 
296
 
 
297
    /* nothing to do */
 
298
    return 0;
 
299
}
 
300
 
 
301
int rcu_pending(int cpu)
 
302
{
 
303
    return __rcu_pending(&rcu_ctrlblk, &per_cpu(rcu_data, cpu));
 
304
}
 
305
 
 
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);
 
315
 
 
316
    return (!!rdp->curlist || rcu_pending(cpu));
 
317
}
 
318
 
 
319
void rcu_check_callbacks(int cpu)
 
320
{
 
321
    raise_softirq(RCU_SOFTIRQ);
 
322
}
 
323
 
 
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
}
 
336
 
 
337
void __devinit rcu_online_cpu(int cpu)
 
338
{
 
339
    struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 
340
 
 
341
    rcu_init_percpu_data(cpu, &rcu_ctrlblk, rdp);
 
342
}
 
343
 
 
344
void __init rcu_init(void)
 
345
{
 
346
    rcu_online_cpu(smp_processor_id());
 
347
    open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
 
348
}