trunk/tests/kernel/test-fair-rwlock.c

   1 /* test-fair-rwlock.c
   2  *
   3  */
   4
   5 #include <linux/module.h>
   6 #include <linux/proc_fs.h>
   7 #include <linux/sched.h>
   8 #include <linux/timex.h>
   9 #include <linux/fair-rwlock.h>
  10 #include <linux/kthread.h>
  11 #include <linux/delay.h>
  12 #include <linux/hardirq.h>
  13 #include <linux/module.h>
  14 #include <linux/percpu.h>
  15 #include <asm/ptrace.h>
  16
  17 #if (NR_CPUS > 64 && (BITS_PER_LONG == 32 || NR_CPUS > 32768))
  18 #error "fair rwlock needs more bits per long to deal with that many CPUs"
  19 #endif
  20
  21 /* Test with no contention duration, in seconds */
  22 #define SINGLE_WRITER_TEST_DURATION 10
  23 #define SINGLE_READER_TEST_DURATION 10
  24 #define MULTIPLE_READERS_TEST_DURATION 10
  25
  26 /* Test duration, in seconds */
  27 #define TEST_DURATION 60
  28
  29 #define THREAD_ROFFSET  1UL
  30 #define THREAD_RMASK    ((NR_CPUS - 1) * THREAD_ROFFSET)
  31 #define SOFTIRQ_ROFFSET (THREAD_RMASK + 1)
  32 #define SOFTIRQ_RMASK   ((NR_CPUS - 1) * SOFTIRQ_ROFFSET)
  33 #define HARDIRQ_ROFFSET ((SOFTIRQ_RMASK | THREAD_RMASK) + 1)
  34 #define HARDIRQ_RMASK   ((NR_CPUS - 1) * HARDIRQ_ROFFSET)
  35
  36 #define SUBSCRIBERS_WOFFSET     \
  37         ((HARDIRQ_RMASK | SOFTIRQ_RMASK | THREAD_RMASK) + 1)
  38 #define SUBSCRIBERS_WMASK       \
  39         ((NR_CPUS - 1) * SUBSCRIBERS_WOFFSET)
  40 #define WRITER_MUTEX            \
  41         ((SUBSCRIBERS_WMASK | HARDIRQ_RMASK | SOFTIRQ_RMASK | THREAD_RMASK) + 1)
  42 #define SOFTIRQ_WMASK   (WRITER_MUTEX << 1)
  43 #define SOFTIRQ_WOFFSET SOFTIRQ_WMASK
  44 #define HARDIRQ_WMASK   (SOFTIRQ_WMASK << 1)
  45 #define HARDIRQ_WOFFSET HARDIRQ_WMASK
  46
  47 #define NR_VARS 100
  48 #define NR_WRITERS 2
  49 #define NR_TRYLOCK_WRITERS 2
  50 #define NR_READERS 4
  51 #define NR_TRYLOCK_READERS 2
  52 #define NR_INTERRUPT_READERS 1
  53 #define NR_TRYLOCK_INTERRUPT_READERS 1
  54
  55 /*
  56  * Writer iteration delay, in us. 0 for busy loop. Caution : writers can
  57  * starve readers.
  58  */
  59 #define WRITER_DELAY 10
  60
  61 static int var[NR_VARS];
  62 static struct task_struct *reader_threads[NR_READERS];
  63 static struct task_struct *trylock_reader_threads[NR_TRYLOCK_READERS];
  64 static struct task_struct *writer_threads[NR_WRITERS];
  65 static struct task_struct *trylock_writer_threads[NR_TRYLOCK_WRITERS];
  66 static struct task_struct *interrupt_reader;
  67 static struct task_struct *trylock_interrupt_reader;
  68
  69 static struct fair_rwlock frwlock = {
  70         .value = ATOMIC_LONG_INIT(0),
  71 };
  72
  73 static cycles_t cycles_calibration_min,
  74         cycles_calibration_avg,
  75         cycles_calibration_max;
  76
  77 static inline cycles_t calibrate_cycles(cycles_t cycles)
  78 {
  79         return cycles - cycles_calibration_avg;
  80 }
  81
  82 struct proc_dir_entry *pentry = NULL;
  83
  84 static int reader_thread(void *data)
  85 {
  86         int i;
  87         int prev, cur;
  88         unsigned long iter = 0;
  89         cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
  90                 delayavg = 0;
  91
  92         printk("reader_thread/%lu runnning\n", (unsigned long)data);
  93         do {
  94                 iter++;
  95                 preempt_disable();      /* for get_cycles accuracy */
  96                 rdtsc_barrier();
  97                 time1 = get_cycles();
  98                 rdtsc_barrier();
  99
 100                 fair_read_lock(&frwlock);
 101
 102                 rdtsc_barrier();
 103                 time2 = get_cycles();
 104                 rdtsc_barrier();
 105                 delay = time2 - time1;
 106                 delaymax = max(delaymax, delay);
 107                 delaymin = min(delaymin, delay);
 108                 delayavg += delay;
 109                 prev = var[0];
 110                 for (i = 1; i < NR_VARS; i++) {
 111                         cur = var[i];
 112                         if (cur != prev)
 113                                 printk(KERN_ALERT
 114                                 "Unequal cur %d/prev %d at i %d, iter %lu "
 115                                 "in thread\n", cur, prev, i, iter);
 116                 }
 117                 fair_read_unlock(&frwlock);
 118                 preempt_enable();       /* for get_cycles accuracy */
 119                 //msleep(100);
 120         } while (!kthread_should_stop());
 121         delayavg /= iter;
 122         printk("reader_thread/%lu iterations : %lu, "
 123                 "lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
 124                 (unsigned long)data, iter,
 125                 calibrate_cycles(delaymin),
 126                 calibrate_cycles(delayavg),
 127                 calibrate_cycles(delaymax));
 128         return 0;
 129 }
 130
 131 static int trylock_reader_thread(void *data)
 132 {
 133         int i;
 134         int prev, cur;
 135         unsigned long iter = 0, success_iter = 0;
 136
 137         printk("trylock_reader_thread/%lu runnning\n", (unsigned long)data);
 138         do {
 139                 while (!fair_read_trylock(&frwlock))
 140                         iter++;
 141                 success_iter++;
 142                 prev = var[0];
 143                 for (i = 1; i < NR_VARS; i++) {
 144                         cur = var[i];
 145                         if (cur != prev)
 146                                 printk(KERN_ALERT
 147                                 "Unequal cur %d/prev %d at i %d, iter %lu "
 148                                 "in thread\n", cur, prev, i, iter);
 149                 }
 150                 fair_read_unlock(&frwlock);
 151                 //msleep(100);
 152         } while (!kthread_should_stop());
 153         printk("trylock_reader_thread/%lu iterations : %lu, "
 154                 "successful iterations : %lu\n",
 155                 (unsigned long)data, iter, success_iter);
 156         return 0;
 157 }
 158
 159 DEFINE_PER_CPU(cycles_t, int_delaymin);
 160 DEFINE_PER_CPU(cycles_t, int_delayavg);
 161 DEFINE_PER_CPU(cycles_t, int_delaymax);
 162 DEFINE_PER_CPU(cycles_t, int_ipi_nr);
 163
 164 static void interrupt_reader_ipi(void *data)
 165 {
 166         int i;
 167         int prev, cur;
 168         cycles_t time1, time2;
 169         cycles_t *delaymax, *delaymin, *delayavg, *ipi_nr, delay;
 170
 171         /*
 172          * Skip the ipi caller, not in irq context.
 173          */
 174         if (!in_irq())
 175                 return;
 176
 177         delaymax = &per_cpu(int_delaymax, smp_processor_id());
 178         delaymin = &per_cpu(int_delaymin, smp_processor_id());
 179         delayavg = &per_cpu(int_delayavg, smp_processor_id());
 180         ipi_nr = &per_cpu(int_ipi_nr, smp_processor_id());
 181
 182         rdtsc_barrier();
 183         time1 = get_cycles();
 184         rdtsc_barrier();
 185
 186         fair_read_lock(&frwlock);
 187
 188         rdtsc_barrier();
 189         time2 = get_cycles();
 190         rdtsc_barrier();
 191         delay = time2 - time1;
 192         *delaymax = max(*delaymax, delay);
 193         *delaymin = min(*delaymin, delay);
 194         *delayavg += delay;
 195         (*ipi_nr)++;
 196         prev = var[0];
 197         for (i = 1; i < NR_VARS; i++) {
 198                 cur = var[i];
 199                 if (cur != prev)
 200                         printk(KERN_ALERT
 201                         "Unequal cur %d/prev %d at i %d in interrupt\n",
 202                                 cur, prev, i);
 203         }
 204         fair_read_unlock(&frwlock);
 205 }
 206
 207 DEFINE_PER_CPU(unsigned long, trylock_int_iter);
 208 DEFINE_PER_CPU(unsigned long, trylock_int_success);
 209
 210 static void trylock_interrupt_reader_ipi(void *data)
 211 {
 212         int i;
 213         int prev, cur;
 214
 215         /*
 216          * Skip the ipi caller, not in irq context.
 217          */
 218         if (!in_irq())
 219                 return;
 220
 221         per_cpu(trylock_int_iter, smp_processor_id())++;
 222         while (!fair_read_trylock(&frwlock))
 223                 per_cpu(trylock_int_iter, smp_processor_id())++;
 224         per_cpu(trylock_int_success, smp_processor_id())++;
 225         prev = var[0];
 226         for (i = 1; i < NR_VARS; i++) {
 227                 cur = var[i];
 228                 if (cur != prev)
 229                         printk(KERN_ALERT
 230                         "Unequal cur %d/prev %d at i %d in interrupt\n",
 231                                 cur, prev, i);
 232         }
 233         fair_read_unlock(&frwlock);
 234 }
 235
 236
 237 static int interrupt_reader_thread(void *data)
 238 {
 239         unsigned long iter = 0;
 240         int i;
 241
 242         for_each_online_cpu(i) {
 243                 per_cpu(int_delaymax, i) = 0;
 244                 per_cpu(int_delaymin, i) = ULLONG_MAX;
 245                 per_cpu(int_delayavg, i) = 0;
 246                 per_cpu(int_ipi_nr, i) = 0;
 247         }
 248         do {
 249                 iter++;
 250                 on_each_cpu(interrupt_reader_ipi, NULL, 0);
 251                 msleep(100);
 252         } while (!kthread_should_stop());
 253         printk("interrupt_reader_thread/%lu iterations : %lu\n",
 254                         (unsigned long)data, iter);
 255         for_each_online_cpu(i) {
 256                 per_cpu(int_delayavg, i) /= per_cpu(int_ipi_nr, i);
 257                 printk("interrupt readers on CPU %i, "
 258                         "lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
 259                         i,
 260                         calibrate_cycles(per_cpu(int_delaymin, i)),
 261                         calibrate_cycles(per_cpu(int_delayavg, i)),
 262                         calibrate_cycles(per_cpu(int_delaymax, i)));
 263         }
 264         return 0;
 265 }
 266
 267 static int trylock_interrupt_reader_thread(void *data)
 268 {
 269         unsigned long iter = 0;
 270         int i;
 271
 272         do {
 273                 iter++;
 274                 on_each_cpu(trylock_interrupt_reader_ipi, NULL, 0);
 275                 msleep(100);
 276         } while (!kthread_should_stop());
 277         printk("trylock_interrupt_reader_thread/%lu iterations : %lu\n",
 278                         (unsigned long)data, iter);
 279         for_each_online_cpu(i) {
 280                 printk("trylock interrupt readers on CPU %i, "
 281                         "iterations %lu, "
 282                         "successful iterations : %lu\n",
 283                         i, per_cpu(trylock_int_iter, i),
 284                         per_cpu(trylock_int_success, i));
 285                 per_cpu(trylock_int_iter, i) = 0;
 286                 per_cpu(trylock_int_success, i) = 0;
 287         }
 288         return 0;
 289 }
 290
 291 static int writer_thread(void *data)
 292 {
 293         int i;
 294         int new;
 295         unsigned long iter = 0;
 296         cycles_t time1, time2, delay, delaymax = 0, delaymin = ULLONG_MAX,
 297                 delayavg = 0;
 298
 299         printk("writer_thread/%lu runnning\n", (unsigned long)data);
 300         do {
 301                 iter++;
 302                 preempt_disable();      /* for get_cycles accuracy */
 303                 rdtsc_barrier();
 304                 time1 = get_cycles();
 305                 rdtsc_barrier();
 306
 307                 fair_write_lock_irq(&frwlock);
 308                 //fair_write_lock(&frwlock);
 309
 310                 rdtsc_barrier();
 311                 time2 = get_cycles();
 312                 rdtsc_barrier();
 313                 delay = time2 - time1;
 314                 delaymax = max(delaymax, delay);
 315                 delaymin = min(delaymin, delay);
 316                 delayavg += delay;
 317                 new = (int)get_cycles();
 318                 for (i = 0; i < NR_VARS; i++) {
 319                         var[i] = new;
 320                 }
 321                 //fair_write_unlock(&frwlock);
 322                 fair_write_unlock_irq(&frwlock);
 323                 preempt_enable();       /* for get_cycles accuracy */
 324                 if (WRITER_DELAY > 0)
 325                         udelay(WRITER_DELAY);
 326         } while (!kthread_should_stop());
 327         delayavg /= iter;
 328         printk("writer_thread/%lu iterations : %lu, "
 329                 "lock delay [min,avg,max] %llu,%llu,%llu cycles\n",
 330                 (unsigned long)data, iter,
 331                 calibrate_cycles(delaymin),
 332                 calibrate_cycles(delayavg),
 333                 calibrate_cycles(delaymax));
 334         return 0;
 335 }
 336
 337 static int trylock_writer_thread(void *data)
 338 {
 339         int i;
 340         int new;
 341         unsigned long iter = 0, success = 0;
 342
 343         printk("trylock_writer_thread/%lu runnning\n", (unsigned long)data);
 344         do {
 345                 fair_write_subscribe(&frwlock);
 346                 while (!fair_write_trylock_subscribed_irq(&frwlock)) {
 347                         iter++;
 348                         continue;
 349                 }
 350                 success++;
 351                 //fair_write_lock(&frwlock);
 352                 new = (int)get_cycles();
 353                 for (i = 0; i < NR_VARS; i++) {
 354                         var[i] = new;
 355                 }
 356                 //fair_write_unlock(&frwlock);
 357                 fair_write_unlock_irq(&frwlock);
 358                 if (WRITER_DELAY > 0)
 359                         udelay(WRITER_DELAY);
 360         } while (!kthread_should_stop());
 361         printk("trylock_writer_thread/%lu iterations : %lu, "
 362                 "successful iterations : %lu\n",
 363                 (unsigned long)data, iter, success);
 364         return 0;
 365 }
 366
 367 static void fair_rwlock_create(void)
 368 {
 369         unsigned long i;
 370
 371         for (i = 0; i < NR_READERS; i++) {
 372                 printk("starting reader thread %lu\n", i);
 373                 reader_threads[i] = kthread_run(reader_thread, (void *)i,
 374                         "frwlock_reader");
 375                 BUG_ON(!reader_threads[i]);
 376         }
 377
 378         for (i = 0; i < NR_TRYLOCK_READERS; i++) {
 379                 printk("starting trylock reader thread %lu\n", i);
 380                 trylock_reader_threads[i] = kthread_run(trylock_reader_thread,
 381                         (void *)i, "frwlock_trylock_reader");
 382                 BUG_ON(!trylock_reader_threads[i]);
 383         }
 384
 385
 386         printk("starting interrupt reader %lu\n", i);
 387         interrupt_reader = kthread_run(interrupt_reader_thread, NULL,
 388                 "frwlock_interrupt_reader");
 389         printk("starting trylock interrupt reader %lu\n", i);
 390         trylock_interrupt_reader = kthread_run(trylock_interrupt_reader_thread,
 391                 NULL, "frwlock_trylock_interrupt_reader");
 392
 393         for (i = 0; i < NR_WRITERS; i++) {
 394                 printk("starting writer thread %lu\n", i);
 395                 writer_threads[i] = kthread_run(writer_thread, (void *)i,
 396                         "frwlock_writer");
 397                 BUG_ON(!writer_threads[i]);
 398         }
 399         for (i = 0; i < NR_TRYLOCK_WRITERS; i++) {
 400                 printk("starting trylock writer thread %lu\n", i);
 401                 trylock_writer_threads[i] = kthread_run(trylock_writer_thread,
 402                         (void *)i, "frwlock_trylock_writer");
 403                 BUG_ON(!trylock_writer_threads[i]);
 404         }
 405 }
 406
 407 static void fair_rwlock_stop(void)
 408 {
 409         unsigned long i;
 410
 411         for (i = 0; i < NR_WRITERS; i++)
 412                 kthread_stop(writer_threads[i]);
 413         for (i = 0; i < NR_TRYLOCK_WRITERS; i++)
 414                 kthread_stop(trylock_writer_threads[i]);
 415         for (i = 0; i < NR_READERS; i++)
 416                 kthread_stop(reader_threads[i]);
 417         for (i = 0; i < NR_TRYLOCK_READERS; i++)
 418                 kthread_stop(trylock_reader_threads[i]);
 419         kthread_stop(interrupt_reader);
 420         kthread_stop(trylock_interrupt_reader);
 421 }
 422
 423
 424 static void perform_test(const char *name, void (*callback)(void))
 425 {
 426         printk("%s\n", name);
 427         callback();
 428 }
 429
 430 static int my_open(struct inode *inode, struct file *file)
 431 {
 432         unsigned long i;
 433         cycles_t time1, time2, delay;
 434
 435         printk("** get_cycles calibration **\n");
 436         cycles_calibration_min = ULLONG_MAX;
 437         cycles_calibration_avg = 0;
 438         cycles_calibration_max = 0;
 439
 440         local_irq_disable();
 441         for (i = 0; i < 10; i++) {
 442                 rdtsc_barrier();
 443                 time1 = get_cycles();
 444                 rdtsc_barrier();
 445                 rdtsc_barrier();
 446                 time2 = get_cycles();
 447                 rdtsc_barrier();
 448                 delay = time2 - time1;
 449                 cycles_calibration_min = min(cycles_calibration_min, delay);
 450                 cycles_calibration_avg += delay;
 451                 cycles_calibration_max = max(cycles_calibration_max, delay);
 452         }
 453         cycles_calibration_avg /= 10;
 454         local_irq_enable();
 455
 456         printk("get_cycles takes [min,avg,max] %llu,%llu,%llu cycles, "
 457                 "results calibrated on avg\n",
 458                 cycles_calibration_min,
 459                 cycles_calibration_avg,
 460                 cycles_calibration_max);
 461
 462         printk("** Single writer test, no contention **\n");
 463         writer_threads[0] = kthread_run(writer_thread, (void *)0,
 464                 "frwlock_writer");
 465         BUG_ON(!writer_threads[0]);
 466         ssleep(SINGLE_WRITER_TEST_DURATION);
 467         kthread_stop(writer_threads[0]);
 468
 469         printk("** Single reader test, no contention **\n");
 470         reader_threads[0] = kthread_run(reader_thread, (void *)0,
 471                 "frwlock_reader");
 472         BUG_ON(!reader_threads[0]);
 473         ssleep(SINGLE_READER_TEST_DURATION);
 474         kthread_stop(reader_threads[0]);
 475
 476         printk("** Multiple readers test, no contention **\n");
 477         for (i = 0; i < NR_READERS; i++) {
 478                 printk("starting reader thread %lu\n", i);
 479                 reader_threads[i] = kthread_run(reader_thread, (void *)i,
 480                         "frwlock_reader");
 481                 BUG_ON(!reader_threads[i]);
 482         }
 483         ssleep(SINGLE_READER_TEST_DURATION);
 484         for (i = 0; i < NR_READERS; i++)
 485                 kthread_stop(reader_threads[i]);
 486
 487         printk("** High contention test **\n");
 488         perform_test("fair-rwlock-create", fair_rwlock_create);
 489         ssleep(TEST_DURATION);
 490         perform_test("fair-rwlock-stop", fair_rwlock_stop);
 491
 492         return -EPERM;
 493 }
 494
 495
 496 static struct file_operations my_operations = {
 497         .open = my_open,
 498 };
 499
 500 int init_module(void)
 501 {
 502         pentry = create_proc_entry("testfrwlock", 0444, NULL);
 503         if (pentry)
 504                 pentry->proc_fops = &my_operations;
 505
 506         printk("NR_CPUS : %d\n", NR_CPUS);
 507         printk("THREAD_ROFFSET : %lX\n", THREAD_ROFFSET);
 508         printk("THREAD_RMASK : %lX\n", THREAD_RMASK);
 509         printk("SOFTIRQ_ROFFSET : %lX\n", SOFTIRQ_ROFFSET);
 510         printk("SOFTIRQ_RMASK : %lX\n", SOFTIRQ_RMASK);
 511         printk("HARDIRQ_ROFFSET : %lX\n", HARDIRQ_ROFFSET);
 512         printk("HARDIRQ_RMASK : %lX\n", HARDIRQ_RMASK);
 513         printk("SUBSCRIBERS_WOFFSET : %lX\n", SUBSCRIBERS_WOFFSET);
 514         printk("SUBSCRIBERS_WMASK : %lX\n", SUBSCRIBERS_WMASK);
 515         printk("WRITER_MUTEX : %lX\n", WRITER_MUTEX);
 516         printk("SOFTIRQ_WMASK : %lX\n", SOFTIRQ_WMASK);
 517         printk("HARDIRQ_WMASK : %lX\n", HARDIRQ_WMASK);
 518
 519         return 0;
 520 }
 521
 522 void cleanup_module(void)
 523 {
 524         remove_proc_entry("testfrwlock", NULL);
 525 }
 526
 527 MODULE_LICENSE("GPL");
 528 MODULE_AUTHOR("Mathieu Desnoyers");
 529 MODULE_DESCRIPTION("Fair rwlock test");