Merge ssh://master.kernel.org/pub/scm/linux/kernel/git/sam/kbuild
[linux-2.6] / kernel / rcutorture.c
1 /*
2  * Read-Copy Update /proc-based torture test facility
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, 2005
19  *
20  * Authors: Paul E. McKenney <paulmck@us.ibm.com>
21  *
22  * See also:  Documentation/RCU/torture.txt
23  */
24 #include <linux/types.h>
25 #include <linux/kernel.h>
26 #include <linux/init.h>
27 #include <linux/module.h>
28 #include <linux/kthread.h>
29 #include <linux/err.h>
30 #include <linux/spinlock.h>
31 #include <linux/smp.h>
32 #include <linux/rcupdate.h>
33 #include <linux/interrupt.h>
34 #include <linux/sched.h>
35 #include <asm/atomic.h>
36 #include <linux/bitops.h>
37 #include <linux/module.h>
38 #include <linux/completion.h>
39 #include <linux/moduleparam.h>
40 #include <linux/percpu.h>
41 #include <linux/notifier.h>
42 #include <linux/cpu.h>
43 #include <linux/random.h>
44 #include <linux/delay.h>
45 #include <linux/byteorder/swabb.h>
46 #include <linux/stat.h>
47
48 MODULE_LICENSE("GPL");
49
50 static int nreaders = -1;       /* # reader threads, defaults to 4*ncpus */
51 static int stat_interval;       /* Interval between stats, in seconds. */
52                                 /*  Defaults to "only at end of test". */
53 static int verbose;             /* Print more debug info. */
54 static int test_no_idle_hz;     /* Test RCU's support for tickless idle CPUs. */
55 static int shuffle_interval = 5; /* Interval between shuffles (in sec)*/
56
57 MODULE_PARM(nreaders, "i");
58 MODULE_PARM_DESC(nreaders, "Number of RCU reader threads");
59 MODULE_PARM(stat_interval, "i");
60 MODULE_PARM_DESC(stat_interval, "Number of seconds between stats printk()s");
61 MODULE_PARM(verbose, "i");
62 MODULE_PARM_DESC(verbose, "Enable verbose debugging printk()s");
63 MODULE_PARM(test_no_idle_hz, "i");
64 MODULE_PARM_DESC(test_no_idle_hz, "Test support for tickless idle CPUs");
65 MODULE_PARM(shuffle_interval, "i");
66 MODULE_PARM_DESC(shuffle_interval, "Number of seconds between shuffles");
67 #define TORTURE_FLAG "rcutorture: "
68 #define PRINTK_STRING(s) \
69         do { printk(KERN_ALERT TORTURE_FLAG s "\n"); } while (0)
70 #define VERBOSE_PRINTK_STRING(s) \
71         do { if (verbose) printk(KERN_ALERT TORTURE_FLAG s "\n"); } while (0)
72 #define VERBOSE_PRINTK_ERRSTRING(s) \
73         do { if (verbose) printk(KERN_ALERT TORTURE_FLAG "!!! " s "\n"); } while (0)
74
75 static char printk_buf[4096];
76
77 static int nrealreaders;
78 static struct task_struct *writer_task;
79 static struct task_struct **reader_tasks;
80 static struct task_struct *stats_task;
81 static struct task_struct *shuffler_task;
82
83 #define RCU_TORTURE_PIPE_LEN 10
84
85 struct rcu_torture {
86         struct rcu_head rtort_rcu;
87         int rtort_pipe_count;
88         struct list_head rtort_free;
89         int rtort_mbtest;
90 };
91
92 static int fullstop = 0;        /* stop generating callbacks at test end. */
93 static LIST_HEAD(rcu_torture_freelist);
94 static struct rcu_torture *rcu_torture_current = NULL;
95 static long rcu_torture_current_version = 0;
96 static struct rcu_torture rcu_tortures[10 * RCU_TORTURE_PIPE_LEN];
97 static DEFINE_SPINLOCK(rcu_torture_lock);
98 static DEFINE_PER_CPU(long [RCU_TORTURE_PIPE_LEN + 1], rcu_torture_count) =
99         { 0 };
100 static DEFINE_PER_CPU(long [RCU_TORTURE_PIPE_LEN + 1], rcu_torture_batch) =
101         { 0 };
102 static atomic_t rcu_torture_wcount[RCU_TORTURE_PIPE_LEN + 1];
103 atomic_t n_rcu_torture_alloc;
104 atomic_t n_rcu_torture_alloc_fail;
105 atomic_t n_rcu_torture_free;
106 atomic_t n_rcu_torture_mberror;
107 atomic_t n_rcu_torture_error;
108
109 /*
110  * Allocate an element from the rcu_tortures pool.
111  */
112 static struct rcu_torture *
113 rcu_torture_alloc(void)
114 {
115         struct list_head *p;
116
117         spin_lock(&rcu_torture_lock);
118         if (list_empty(&rcu_torture_freelist)) {
119                 atomic_inc(&n_rcu_torture_alloc_fail);
120                 spin_unlock(&rcu_torture_lock);
121                 return NULL;
122         }
123         atomic_inc(&n_rcu_torture_alloc);
124         p = rcu_torture_freelist.next;
125         list_del_init(p);
126         spin_unlock(&rcu_torture_lock);
127         return container_of(p, struct rcu_torture, rtort_free);
128 }
129
130 /*
131  * Free an element to the rcu_tortures pool.
132  */
133 static void
134 rcu_torture_free(struct rcu_torture *p)
135 {
136         atomic_inc(&n_rcu_torture_free);
137         spin_lock(&rcu_torture_lock);
138         list_add_tail(&p->rtort_free, &rcu_torture_freelist);
139         spin_unlock(&rcu_torture_lock);
140 }
141
142 static void
143 rcu_torture_cb(struct rcu_head *p)
144 {
145         int i;
146         struct rcu_torture *rp = container_of(p, struct rcu_torture, rtort_rcu);
147
148         if (fullstop) {
149                 /* Test is ending, just drop callbacks on the floor. */
150                 /* The next initialization will pick up the pieces. */
151                 return;
152         }
153         i = rp->rtort_pipe_count;
154         if (i > RCU_TORTURE_PIPE_LEN)
155                 i = RCU_TORTURE_PIPE_LEN;
156         atomic_inc(&rcu_torture_wcount[i]);
157         if (++rp->rtort_pipe_count >= RCU_TORTURE_PIPE_LEN) {
158                 rp->rtort_mbtest = 0;
159                 rcu_torture_free(rp);
160         } else
161                 call_rcu(p, rcu_torture_cb);
162 }
163
164 struct rcu_random_state {
165         unsigned long rrs_state;
166         unsigned long rrs_count;
167 };
168
169 #define RCU_RANDOM_MULT 39916801  /* prime */
170 #define RCU_RANDOM_ADD  479001701 /* prime */
171 #define RCU_RANDOM_REFRESH 10000
172
173 #define DEFINE_RCU_RANDOM(name) struct rcu_random_state name = { 0, 0 }
174
175 /*
176  * Crude but fast random-number generator.  Uses a linear congruential
177  * generator, with occasional help from get_random_bytes().
178  */
179 static long
180 rcu_random(struct rcu_random_state *rrsp)
181 {
182         long refresh;
183
184         if (--rrsp->rrs_count < 0) {
185                 get_random_bytes(&refresh, sizeof(refresh));
186                 rrsp->rrs_state += refresh;
187                 rrsp->rrs_count = RCU_RANDOM_REFRESH;
188         }
189         rrsp->rrs_state = rrsp->rrs_state * RCU_RANDOM_MULT + RCU_RANDOM_ADD;
190         return swahw32(rrsp->rrs_state);
191 }
192
193 /*
194  * RCU torture writer kthread.  Repeatedly substitutes a new structure
195  * for that pointed to by rcu_torture_current, freeing the old structure
196  * after a series of grace periods (the "pipeline").
197  */
198 static int
199 rcu_torture_writer(void *arg)
200 {
201         int i;
202         long oldbatch = rcu_batches_completed();
203         struct rcu_torture *rp;
204         struct rcu_torture *old_rp;
205         static DEFINE_RCU_RANDOM(rand);
206
207         VERBOSE_PRINTK_STRING("rcu_torture_writer task started");
208         set_user_nice(current, 19);
209
210         do {
211                 schedule_timeout_uninterruptible(1);
212                 if (rcu_batches_completed() == oldbatch)
213                         continue;
214                 if ((rp = rcu_torture_alloc()) == NULL)
215                         continue;
216                 rp->rtort_pipe_count = 0;
217                 udelay(rcu_random(&rand) & 0x3ff);
218                 old_rp = rcu_torture_current;
219                 rp->rtort_mbtest = 1;
220                 rcu_assign_pointer(rcu_torture_current, rp);
221                 smp_wmb();
222                 if (old_rp != NULL) {
223                         i = old_rp->rtort_pipe_count;
224                         if (i > RCU_TORTURE_PIPE_LEN)
225                                 i = RCU_TORTURE_PIPE_LEN;
226                         atomic_inc(&rcu_torture_wcount[i]);
227                         old_rp->rtort_pipe_count++;
228                         call_rcu(&old_rp->rtort_rcu, rcu_torture_cb);
229                 }
230                 rcu_torture_current_version++;
231                 oldbatch = rcu_batches_completed();
232         } while (!kthread_should_stop() && !fullstop);
233         VERBOSE_PRINTK_STRING("rcu_torture_writer task stopping");
234         while (!kthread_should_stop())
235                 schedule_timeout_uninterruptible(1);
236         return 0;
237 }
238
239 /*
240  * RCU torture reader kthread.  Repeatedly dereferences rcu_torture_current,
241  * incrementing the corresponding element of the pipeline array.  The
242  * counter in the element should never be greater than 1, otherwise, the
243  * RCU implementation is broken.
244  */
245 static int
246 rcu_torture_reader(void *arg)
247 {
248         int completed;
249         DEFINE_RCU_RANDOM(rand);
250         struct rcu_torture *p;
251         int pipe_count;
252
253         VERBOSE_PRINTK_STRING("rcu_torture_reader task started");
254         set_user_nice(current, 19);
255
256         do {
257                 rcu_read_lock();
258                 completed = rcu_batches_completed();
259                 p = rcu_dereference(rcu_torture_current);
260                 if (p == NULL) {
261                         /* Wait for rcu_torture_writer to get underway */
262                         rcu_read_unlock();
263                         schedule_timeout_interruptible(HZ);
264                         continue;
265                 }
266                 if (p->rtort_mbtest == 0)
267                         atomic_inc(&n_rcu_torture_mberror);
268                 udelay(rcu_random(&rand) & 0x7f);
269                 preempt_disable();
270                 pipe_count = p->rtort_pipe_count;
271                 if (pipe_count > RCU_TORTURE_PIPE_LEN) {
272                         /* Should not happen, but... */
273                         pipe_count = RCU_TORTURE_PIPE_LEN;
274                 }
275                 ++__get_cpu_var(rcu_torture_count)[pipe_count];
276                 completed = rcu_batches_completed() - completed;
277                 if (completed > RCU_TORTURE_PIPE_LEN) {
278                         /* Should not happen, but... */
279                         completed = RCU_TORTURE_PIPE_LEN;
280                 }
281                 ++__get_cpu_var(rcu_torture_batch)[completed];
282                 preempt_enable();
283                 rcu_read_unlock();
284                 schedule();
285         } while (!kthread_should_stop() && !fullstop);
286         VERBOSE_PRINTK_STRING("rcu_torture_reader task stopping");
287         while (!kthread_should_stop())
288                 schedule_timeout_uninterruptible(1);
289         return 0;
290 }
291
292 /*
293  * Create an RCU-torture statistics message in the specified buffer.
294  */
295 static int
296 rcu_torture_printk(char *page)
297 {
298         int cnt = 0;
299         int cpu;
300         int i;
301         long pipesummary[RCU_TORTURE_PIPE_LEN + 1] = { 0 };
302         long batchsummary[RCU_TORTURE_PIPE_LEN + 1] = { 0 };
303
304         for_each_cpu(cpu) {
305                 for (i = 0; i < RCU_TORTURE_PIPE_LEN + 1; i++) {
306                         pipesummary[i] += per_cpu(rcu_torture_count, cpu)[i];
307                         batchsummary[i] += per_cpu(rcu_torture_batch, cpu)[i];
308                 }
309         }
310         for (i = RCU_TORTURE_PIPE_LEN - 1; i >= 0; i--) {
311                 if (pipesummary[i] != 0)
312                         break;
313         }
314         cnt += sprintf(&page[cnt], "rcutorture: ");
315         cnt += sprintf(&page[cnt],
316                        "rtc: %p ver: %ld tfle: %d rta: %d rtaf: %d rtf: %d "
317                        "rtmbe: %d",
318                        rcu_torture_current,
319                        rcu_torture_current_version,
320                        list_empty(&rcu_torture_freelist),
321                        atomic_read(&n_rcu_torture_alloc),
322                        atomic_read(&n_rcu_torture_alloc_fail),
323                        atomic_read(&n_rcu_torture_free),
324                        atomic_read(&n_rcu_torture_mberror));
325         if (atomic_read(&n_rcu_torture_mberror) != 0)
326                 cnt += sprintf(&page[cnt], " !!!");
327         cnt += sprintf(&page[cnt], "\nrcutorture: ");
328         if (i > 1) {
329                 cnt += sprintf(&page[cnt], "!!! ");
330                 atomic_inc(&n_rcu_torture_error);
331         }
332         cnt += sprintf(&page[cnt], "Reader Pipe: ");
333         for (i = 0; i < RCU_TORTURE_PIPE_LEN + 1; i++)
334                 cnt += sprintf(&page[cnt], " %ld", pipesummary[i]);
335         cnt += sprintf(&page[cnt], "\nrcutorture: ");
336         cnt += sprintf(&page[cnt], "Reader Batch: ");
337         for (i = 0; i < RCU_TORTURE_PIPE_LEN; i++)
338                 cnt += sprintf(&page[cnt], " %ld", batchsummary[i]);
339         cnt += sprintf(&page[cnt], "\nrcutorture: ");
340         cnt += sprintf(&page[cnt], "Free-Block Circulation: ");
341         for (i = 0; i < RCU_TORTURE_PIPE_LEN + 1; i++) {
342                 cnt += sprintf(&page[cnt], " %d",
343                                atomic_read(&rcu_torture_wcount[i]));
344         }
345         cnt += sprintf(&page[cnt], "\n");
346         return cnt;
347 }
348
349 /*
350  * Print torture statistics.  Caller must ensure that there is only
351  * one call to this function at a given time!!!  This is normally
352  * accomplished by relying on the module system to only have one copy
353  * of the module loaded, and then by giving the rcu_torture_stats
354  * kthread full control (or the init/cleanup functions when rcu_torture_stats
355  * thread is not running).
356  */
357 static void
358 rcu_torture_stats_print(void)
359 {
360         int cnt;
361
362         cnt = rcu_torture_printk(printk_buf);
363         printk(KERN_ALERT "%s", printk_buf);
364 }
365
366 /*
367  * Periodically prints torture statistics, if periodic statistics printing
368  * was specified via the stat_interval module parameter.
369  *
370  * No need to worry about fullstop here, since this one doesn't reference
371  * volatile state or register callbacks.
372  */
373 static int
374 rcu_torture_stats(void *arg)
375 {
376         VERBOSE_PRINTK_STRING("rcu_torture_stats task started");
377         do {
378                 schedule_timeout_interruptible(stat_interval * HZ);
379                 rcu_torture_stats_print();
380         } while (!kthread_should_stop());
381         VERBOSE_PRINTK_STRING("rcu_torture_stats task stopping");
382         return 0;
383 }
384
385 static int rcu_idle_cpu;        /* Force all torture tasks off this CPU */
386
387 /* Shuffle tasks such that we allow @rcu_idle_cpu to become idle. A special case
388  * is when @rcu_idle_cpu = -1, when we allow the tasks to run on all CPUs.
389  */
390 void rcu_torture_shuffle_tasks(void)
391 {
392         cpumask_t tmp_mask = CPU_MASK_ALL;
393         int i;
394
395         lock_cpu_hotplug();
396
397         /* No point in shuffling if there is only one online CPU (ex: UP) */
398         if (num_online_cpus() == 1) {
399                 unlock_cpu_hotplug();
400                 return;
401         }
402
403         if (rcu_idle_cpu != -1)
404                 cpu_clear(rcu_idle_cpu, tmp_mask);
405
406         set_cpus_allowed(current, tmp_mask);
407
408         if (reader_tasks != NULL) {
409                 for (i = 0; i < nrealreaders; i++)
410                         if (reader_tasks[i])
411                                 set_cpus_allowed(reader_tasks[i], tmp_mask);
412         }
413
414         if (writer_task)
415                 set_cpus_allowed(writer_task, tmp_mask);
416
417         if (stats_task)
418                 set_cpus_allowed(stats_task, tmp_mask);
419
420         if (rcu_idle_cpu == -1)
421                 rcu_idle_cpu = num_online_cpus() - 1;
422         else
423                 rcu_idle_cpu--;
424
425         unlock_cpu_hotplug();
426 }
427
428 /* Shuffle tasks across CPUs, with the intent of allowing each CPU in the
429  * system to become idle at a time and cut off its timer ticks. This is meant
430  * to test the support for such tickless idle CPU in RCU.
431  */
432 static int
433 rcu_torture_shuffle(void *arg)
434 {
435         VERBOSE_PRINTK_STRING("rcu_torture_shuffle task started");
436         do {
437                 schedule_timeout_interruptible(shuffle_interval * HZ);
438                 rcu_torture_shuffle_tasks();
439         } while (!kthread_should_stop());
440         VERBOSE_PRINTK_STRING("rcu_torture_shuffle task stopping");
441         return 0;
442 }
443
444 static void
445 rcu_torture_cleanup(void)
446 {
447         int i;
448
449         fullstop = 1;
450         if (shuffler_task != NULL) {
451                 VERBOSE_PRINTK_STRING("Stopping rcu_torture_shuffle task");
452                 kthread_stop(shuffler_task);
453         }
454         shuffler_task = NULL;
455
456         if (writer_task != NULL) {
457                 VERBOSE_PRINTK_STRING("Stopping rcu_torture_writer task");
458                 kthread_stop(writer_task);
459         }
460         writer_task = NULL;
461
462         if (reader_tasks != NULL) {
463                 for (i = 0; i < nrealreaders; i++) {
464                         if (reader_tasks[i] != NULL) {
465                                 VERBOSE_PRINTK_STRING(
466                                         "Stopping rcu_torture_reader task");
467                                 kthread_stop(reader_tasks[i]);
468                         }
469                         reader_tasks[i] = NULL;
470                 }
471                 kfree(reader_tasks);
472                 reader_tasks = NULL;
473         }
474         rcu_torture_current = NULL;
475
476         if (stats_task != NULL) {
477                 VERBOSE_PRINTK_STRING("Stopping rcu_torture_stats task");
478                 kthread_stop(stats_task);
479         }
480         stats_task = NULL;
481
482         /* Wait for all RCU callbacks to fire.  */
483         rcu_barrier();
484
485         rcu_torture_stats_print();  /* -After- the stats thread is stopped! */
486         printk(KERN_ALERT TORTURE_FLAG
487                "--- End of test: %s\n",
488                atomic_read(&n_rcu_torture_error) == 0 ? "SUCCESS" : "FAILURE");
489 }
490
491 static int
492 rcu_torture_init(void)
493 {
494         int i;
495         int cpu;
496         int firsterr = 0;
497
498         /* Process args and tell the world that the torturer is on the job. */
499
500         if (nreaders >= 0)
501                 nrealreaders = nreaders;
502         else
503                 nrealreaders = 2 * num_online_cpus();
504         printk(KERN_ALERT TORTURE_FLAG "--- Start of test: nreaders=%d "
505                 "stat_interval=%d verbose=%d test_no_idle_hz=%d "
506                 "shuffle_interval = %d\n",
507                 nrealreaders, stat_interval, verbose, test_no_idle_hz,
508                 shuffle_interval);
509         fullstop = 0;
510
511         /* Set up the freelist. */
512
513         INIT_LIST_HEAD(&rcu_torture_freelist);
514         for (i = 0; i < sizeof(rcu_tortures) / sizeof(rcu_tortures[0]); i++) {
515                 rcu_tortures[i].rtort_mbtest = 0;
516                 list_add_tail(&rcu_tortures[i].rtort_free,
517                               &rcu_torture_freelist);
518         }
519
520         /* Initialize the statistics so that each run gets its own numbers. */
521
522         rcu_torture_current = NULL;
523         rcu_torture_current_version = 0;
524         atomic_set(&n_rcu_torture_alloc, 0);
525         atomic_set(&n_rcu_torture_alloc_fail, 0);
526         atomic_set(&n_rcu_torture_free, 0);
527         atomic_set(&n_rcu_torture_mberror, 0);
528         atomic_set(&n_rcu_torture_error, 0);
529         for (i = 0; i < RCU_TORTURE_PIPE_LEN + 1; i++)
530                 atomic_set(&rcu_torture_wcount[i], 0);
531         for_each_cpu(cpu) {
532                 for (i = 0; i < RCU_TORTURE_PIPE_LEN + 1; i++) {
533                         per_cpu(rcu_torture_count, cpu)[i] = 0;
534                         per_cpu(rcu_torture_batch, cpu)[i] = 0;
535                 }
536         }
537
538         /* Start up the kthreads. */
539
540         VERBOSE_PRINTK_STRING("Creating rcu_torture_writer task");
541         writer_task = kthread_run(rcu_torture_writer, NULL,
542                                   "rcu_torture_writer");
543         if (IS_ERR(writer_task)) {
544                 firsterr = PTR_ERR(writer_task);
545                 VERBOSE_PRINTK_ERRSTRING("Failed to create writer");
546                 writer_task = NULL;
547                 goto unwind;
548         }
549         reader_tasks = kmalloc(nrealreaders * sizeof(reader_tasks[0]),
550                                GFP_KERNEL);
551         if (reader_tasks == NULL) {
552                 VERBOSE_PRINTK_ERRSTRING("out of memory");
553                 firsterr = -ENOMEM;
554                 goto unwind;
555         }
556         for (i = 0; i < nrealreaders; i++) {
557                 VERBOSE_PRINTK_STRING("Creating rcu_torture_reader task");
558                 reader_tasks[i] = kthread_run(rcu_torture_reader, NULL,
559                                               "rcu_torture_reader");
560                 if (IS_ERR(reader_tasks[i])) {
561                         firsterr = PTR_ERR(reader_tasks[i]);
562                         VERBOSE_PRINTK_ERRSTRING("Failed to create reader");
563                         reader_tasks[i] = NULL;
564                         goto unwind;
565                 }
566         }
567         if (stat_interval > 0) {
568                 VERBOSE_PRINTK_STRING("Creating rcu_torture_stats task");
569                 stats_task = kthread_run(rcu_torture_stats, NULL,
570                                         "rcu_torture_stats");
571                 if (IS_ERR(stats_task)) {
572                         firsterr = PTR_ERR(stats_task);
573                         VERBOSE_PRINTK_ERRSTRING("Failed to create stats");
574                         stats_task = NULL;
575                         goto unwind;
576                 }
577         }
578         if (test_no_idle_hz) {
579                 rcu_idle_cpu = num_online_cpus() - 1;
580                 /* Create the shuffler thread */
581                 shuffler_task = kthread_run(rcu_torture_shuffle, NULL,
582                                           "rcu_torture_shuffle");
583                 if (IS_ERR(shuffler_task)) {
584                         firsterr = PTR_ERR(shuffler_task);
585                         VERBOSE_PRINTK_ERRSTRING("Failed to create shuffler");
586                         shuffler_task = NULL;
587                         goto unwind;
588                 }
589         }
590         return 0;
591
592 unwind:
593         rcu_torture_cleanup();
594         return firsterr;
595 }
596
597 module_init(rcu_torture_init);
598 module_exit(rcu_torture_cleanup);