arm64: dts: qcom: sm8550: add TRNG node
[linux-modified.git] / kernel / locking / test-ww_mutex.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3  * Module-based API test facility for ww_mutexes
4  */
5
6 #include <linux/kernel.h>
7
8 #include <linux/completion.h>
9 #include <linux/delay.h>
10 #include <linux/kthread.h>
11 #include <linux/module.h>
12 #include <linux/prandom.h>
13 #include <linux/slab.h>
14 #include <linux/ww_mutex.h>
15
16 static DEFINE_WD_CLASS(ww_class);
17 struct workqueue_struct *wq;
18
19 #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
20 #define ww_acquire_init_noinject(a, b) do { \
21                 ww_acquire_init((a), (b)); \
22                 (a)->deadlock_inject_countdown = ~0U; \
23         } while (0)
24 #else
25 #define ww_acquire_init_noinject(a, b) ww_acquire_init((a), (b))
26 #endif
27
28 struct test_mutex {
29         struct work_struct work;
30         struct ww_mutex mutex;
31         struct completion ready, go, done;
32         unsigned int flags;
33 };
34
35 #define TEST_MTX_SPIN BIT(0)
36 #define TEST_MTX_TRY BIT(1)
37 #define TEST_MTX_CTX BIT(2)
38 #define __TEST_MTX_LAST BIT(3)
39
40 static void test_mutex_work(struct work_struct *work)
41 {
42         struct test_mutex *mtx = container_of(work, typeof(*mtx), work);
43
44         complete(&mtx->ready);
45         wait_for_completion(&mtx->go);
46
47         if (mtx->flags & TEST_MTX_TRY) {
48                 while (!ww_mutex_trylock(&mtx->mutex, NULL))
49                         cond_resched();
50         } else {
51                 ww_mutex_lock(&mtx->mutex, NULL);
52         }
53         complete(&mtx->done);
54         ww_mutex_unlock(&mtx->mutex);
55 }
56
57 static int __test_mutex(unsigned int flags)
58 {
59 #define TIMEOUT (HZ / 16)
60         struct test_mutex mtx;
61         struct ww_acquire_ctx ctx;
62         int ret;
63
64         ww_mutex_init(&mtx.mutex, &ww_class);
65         ww_acquire_init(&ctx, &ww_class);
66
67         INIT_WORK_ONSTACK(&mtx.work, test_mutex_work);
68         init_completion(&mtx.ready);
69         init_completion(&mtx.go);
70         init_completion(&mtx.done);
71         mtx.flags = flags;
72
73         schedule_work(&mtx.work);
74
75         wait_for_completion(&mtx.ready);
76         ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL);
77         complete(&mtx.go);
78         if (flags & TEST_MTX_SPIN) {
79                 unsigned long timeout = jiffies + TIMEOUT;
80
81                 ret = 0;
82                 do {
83                         if (completion_done(&mtx.done)) {
84                                 ret = -EINVAL;
85                                 break;
86                         }
87                         cond_resched();
88                 } while (time_before(jiffies, timeout));
89         } else {
90                 ret = wait_for_completion_timeout(&mtx.done, TIMEOUT);
91         }
92         ww_mutex_unlock(&mtx.mutex);
93         ww_acquire_fini(&ctx);
94
95         if (ret) {
96                 pr_err("%s(flags=%x): mutual exclusion failure\n",
97                        __func__, flags);
98                 ret = -EINVAL;
99         }
100
101         flush_work(&mtx.work);
102         destroy_work_on_stack(&mtx.work);
103         return ret;
104 #undef TIMEOUT
105 }
106
107 static int test_mutex(void)
108 {
109         int ret;
110         int i;
111
112         for (i = 0; i < __TEST_MTX_LAST; i++) {
113                 ret = __test_mutex(i);
114                 if (ret)
115                         return ret;
116         }
117
118         return 0;
119 }
120
121 static int test_aa(bool trylock)
122 {
123         struct ww_mutex mutex;
124         struct ww_acquire_ctx ctx;
125         int ret;
126         const char *from = trylock ? "trylock" : "lock";
127
128         ww_mutex_init(&mutex, &ww_class);
129         ww_acquire_init(&ctx, &ww_class);
130
131         if (!trylock) {
132                 ret = ww_mutex_lock(&mutex, &ctx);
133                 if (ret) {
134                         pr_err("%s: initial lock failed!\n", __func__);
135                         goto out;
136                 }
137         } else {
138                 ret = !ww_mutex_trylock(&mutex, &ctx);
139                 if (ret) {
140                         pr_err("%s: initial trylock failed!\n", __func__);
141                         goto out;
142                 }
143         }
144
145         if (ww_mutex_trylock(&mutex, NULL))  {
146                 pr_err("%s: trylocked itself without context from %s!\n", __func__, from);
147                 ww_mutex_unlock(&mutex);
148                 ret = -EINVAL;
149                 goto out;
150         }
151
152         if (ww_mutex_trylock(&mutex, &ctx))  {
153                 pr_err("%s: trylocked itself with context from %s!\n", __func__, from);
154                 ww_mutex_unlock(&mutex);
155                 ret = -EINVAL;
156                 goto out;
157         }
158
159         ret = ww_mutex_lock(&mutex, &ctx);
160         if (ret != -EALREADY) {
161                 pr_err("%s: missed deadlock for recursing, ret=%d from %s\n",
162                        __func__, ret, from);
163                 if (!ret)
164                         ww_mutex_unlock(&mutex);
165                 ret = -EINVAL;
166                 goto out;
167         }
168
169         ww_mutex_unlock(&mutex);
170         ret = 0;
171 out:
172         ww_acquire_fini(&ctx);
173         return ret;
174 }
175
176 struct test_abba {
177         struct work_struct work;
178         struct ww_mutex a_mutex;
179         struct ww_mutex b_mutex;
180         struct completion a_ready;
181         struct completion b_ready;
182         bool resolve, trylock;
183         int result;
184 };
185
186 static void test_abba_work(struct work_struct *work)
187 {
188         struct test_abba *abba = container_of(work, typeof(*abba), work);
189         struct ww_acquire_ctx ctx;
190         int err;
191
192         ww_acquire_init_noinject(&ctx, &ww_class);
193         if (!abba->trylock)
194                 ww_mutex_lock(&abba->b_mutex, &ctx);
195         else
196                 WARN_ON(!ww_mutex_trylock(&abba->b_mutex, &ctx));
197
198         WARN_ON(READ_ONCE(abba->b_mutex.ctx) != &ctx);
199
200         complete(&abba->b_ready);
201         wait_for_completion(&abba->a_ready);
202
203         err = ww_mutex_lock(&abba->a_mutex, &ctx);
204         if (abba->resolve && err == -EDEADLK) {
205                 ww_mutex_unlock(&abba->b_mutex);
206                 ww_mutex_lock_slow(&abba->a_mutex, &ctx);
207                 err = ww_mutex_lock(&abba->b_mutex, &ctx);
208         }
209
210         if (!err)
211                 ww_mutex_unlock(&abba->a_mutex);
212         ww_mutex_unlock(&abba->b_mutex);
213         ww_acquire_fini(&ctx);
214
215         abba->result = err;
216 }
217
218 static int test_abba(bool trylock, bool resolve)
219 {
220         struct test_abba abba;
221         struct ww_acquire_ctx ctx;
222         int err, ret;
223
224         ww_mutex_init(&abba.a_mutex, &ww_class);
225         ww_mutex_init(&abba.b_mutex, &ww_class);
226         INIT_WORK_ONSTACK(&abba.work, test_abba_work);
227         init_completion(&abba.a_ready);
228         init_completion(&abba.b_ready);
229         abba.trylock = trylock;
230         abba.resolve = resolve;
231
232         schedule_work(&abba.work);
233
234         ww_acquire_init_noinject(&ctx, &ww_class);
235         if (!trylock)
236                 ww_mutex_lock(&abba.a_mutex, &ctx);
237         else
238                 WARN_ON(!ww_mutex_trylock(&abba.a_mutex, &ctx));
239
240         WARN_ON(READ_ONCE(abba.a_mutex.ctx) != &ctx);
241
242         complete(&abba.a_ready);
243         wait_for_completion(&abba.b_ready);
244
245         err = ww_mutex_lock(&abba.b_mutex, &ctx);
246         if (resolve && err == -EDEADLK) {
247                 ww_mutex_unlock(&abba.a_mutex);
248                 ww_mutex_lock_slow(&abba.b_mutex, &ctx);
249                 err = ww_mutex_lock(&abba.a_mutex, &ctx);
250         }
251
252         if (!err)
253                 ww_mutex_unlock(&abba.b_mutex);
254         ww_mutex_unlock(&abba.a_mutex);
255         ww_acquire_fini(&ctx);
256
257         flush_work(&abba.work);
258         destroy_work_on_stack(&abba.work);
259
260         ret = 0;
261         if (resolve) {
262                 if (err || abba.result) {
263                         pr_err("%s: failed to resolve ABBA deadlock, A err=%d, B err=%d\n",
264                                __func__, err, abba.result);
265                         ret = -EINVAL;
266                 }
267         } else {
268                 if (err != -EDEADLK && abba.result != -EDEADLK) {
269                         pr_err("%s: missed ABBA deadlock, A err=%d, B err=%d\n",
270                                __func__, err, abba.result);
271                         ret = -EINVAL;
272                 }
273         }
274         return ret;
275 }
276
277 struct test_cycle {
278         struct work_struct work;
279         struct ww_mutex a_mutex;
280         struct ww_mutex *b_mutex;
281         struct completion *a_signal;
282         struct completion b_signal;
283         int result;
284 };
285
286 static void test_cycle_work(struct work_struct *work)
287 {
288         struct test_cycle *cycle = container_of(work, typeof(*cycle), work);
289         struct ww_acquire_ctx ctx;
290         int err, erra = 0;
291
292         ww_acquire_init_noinject(&ctx, &ww_class);
293         ww_mutex_lock(&cycle->a_mutex, &ctx);
294
295         complete(cycle->a_signal);
296         wait_for_completion(&cycle->b_signal);
297
298         err = ww_mutex_lock(cycle->b_mutex, &ctx);
299         if (err == -EDEADLK) {
300                 err = 0;
301                 ww_mutex_unlock(&cycle->a_mutex);
302                 ww_mutex_lock_slow(cycle->b_mutex, &ctx);
303                 erra = ww_mutex_lock(&cycle->a_mutex, &ctx);
304         }
305
306         if (!err)
307                 ww_mutex_unlock(cycle->b_mutex);
308         if (!erra)
309                 ww_mutex_unlock(&cycle->a_mutex);
310         ww_acquire_fini(&ctx);
311
312         cycle->result = err ?: erra;
313 }
314
315 static int __test_cycle(unsigned int nthreads)
316 {
317         struct test_cycle *cycles;
318         unsigned int n, last = nthreads - 1;
319         int ret;
320
321         cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL);
322         if (!cycles)
323                 return -ENOMEM;
324
325         for (n = 0; n < nthreads; n++) {
326                 struct test_cycle *cycle = &cycles[n];
327
328                 ww_mutex_init(&cycle->a_mutex, &ww_class);
329                 if (n == last)
330                         cycle->b_mutex = &cycles[0].a_mutex;
331                 else
332                         cycle->b_mutex = &cycles[n + 1].a_mutex;
333
334                 if (n == 0)
335                         cycle->a_signal = &cycles[last].b_signal;
336                 else
337                         cycle->a_signal = &cycles[n - 1].b_signal;
338                 init_completion(&cycle->b_signal);
339
340                 INIT_WORK(&cycle->work, test_cycle_work);
341                 cycle->result = 0;
342         }
343
344         for (n = 0; n < nthreads; n++)
345                 queue_work(wq, &cycles[n].work);
346
347         flush_workqueue(wq);
348
349         ret = 0;
350         for (n = 0; n < nthreads; n++) {
351                 struct test_cycle *cycle = &cycles[n];
352
353                 if (!cycle->result)
354                         continue;
355
356                 pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n",
357                        n, nthreads, cycle->result);
358                 ret = -EINVAL;
359                 break;
360         }
361
362         for (n = 0; n < nthreads; n++)
363                 ww_mutex_destroy(&cycles[n].a_mutex);
364         kfree(cycles);
365         return ret;
366 }
367
368 static int test_cycle(unsigned int ncpus)
369 {
370         unsigned int n;
371         int ret;
372
373         for (n = 2; n <= ncpus + 1; n++) {
374                 ret = __test_cycle(n);
375                 if (ret)
376                         return ret;
377         }
378
379         return 0;
380 }
381
382 struct stress {
383         struct work_struct work;
384         struct ww_mutex *locks;
385         unsigned long timeout;
386         int nlocks;
387 };
388
389 struct rnd_state rng;
390 DEFINE_SPINLOCK(rng_lock);
391
392 static inline u32 prandom_u32_below(u32 ceil)
393 {
394         u32 ret;
395
396         spin_lock(&rng_lock);
397         ret = prandom_u32_state(&rng) % ceil;
398         spin_unlock(&rng_lock);
399         return ret;
400 }
401
402 static int *get_random_order(int count)
403 {
404         int *order;
405         int n, r, tmp;
406
407         order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);
408         if (!order)
409                 return order;
410
411         for (n = 0; n < count; n++)
412                 order[n] = n;
413
414         for (n = count - 1; n > 1; n--) {
415                 r = prandom_u32_below(n + 1);
416                 if (r != n) {
417                         tmp = order[n];
418                         order[n] = order[r];
419                         order[r] = tmp;
420                 }
421         }
422
423         return order;
424 }
425
426 static void dummy_load(struct stress *stress)
427 {
428         usleep_range(1000, 2000);
429 }
430
431 static void stress_inorder_work(struct work_struct *work)
432 {
433         struct stress *stress = container_of(work, typeof(*stress), work);
434         const int nlocks = stress->nlocks;
435         struct ww_mutex *locks = stress->locks;
436         struct ww_acquire_ctx ctx;
437         int *order;
438
439         order = get_random_order(nlocks);
440         if (!order)
441                 return;
442
443         do {
444                 int contended = -1;
445                 int n, err;
446
447                 ww_acquire_init(&ctx, &ww_class);
448 retry:
449                 err = 0;
450                 for (n = 0; n < nlocks; n++) {
451                         if (n == contended)
452                                 continue;
453
454                         err = ww_mutex_lock(&locks[order[n]], &ctx);
455                         if (err < 0)
456                                 break;
457                 }
458                 if (!err)
459                         dummy_load(stress);
460
461                 if (contended > n)
462                         ww_mutex_unlock(&locks[order[contended]]);
463                 contended = n;
464                 while (n--)
465                         ww_mutex_unlock(&locks[order[n]]);
466
467                 if (err == -EDEADLK) {
468                         if (!time_after(jiffies, stress->timeout)) {
469                                 ww_mutex_lock_slow(&locks[order[contended]], &ctx);
470                                 goto retry;
471                         }
472                 }
473
474                 ww_acquire_fini(&ctx);
475                 if (err) {
476                         pr_err_once("stress (%s) failed with %d\n",
477                                     __func__, err);
478                         break;
479                 }
480         } while (!time_after(jiffies, stress->timeout));
481
482         kfree(order);
483 }
484
485 struct reorder_lock {
486         struct list_head link;
487         struct ww_mutex *lock;
488 };
489
490 static void stress_reorder_work(struct work_struct *work)
491 {
492         struct stress *stress = container_of(work, typeof(*stress), work);
493         LIST_HEAD(locks);
494         struct ww_acquire_ctx ctx;
495         struct reorder_lock *ll, *ln;
496         int *order;
497         int n, err;
498
499         order = get_random_order(stress->nlocks);
500         if (!order)
501                 return;
502
503         for (n = 0; n < stress->nlocks; n++) {
504                 ll = kmalloc(sizeof(*ll), GFP_KERNEL);
505                 if (!ll)
506                         goto out;
507
508                 ll->lock = &stress->locks[order[n]];
509                 list_add(&ll->link, &locks);
510         }
511         kfree(order);
512         order = NULL;
513
514         do {
515                 ww_acquire_init(&ctx, &ww_class);
516
517                 list_for_each_entry(ll, &locks, link) {
518                         err = ww_mutex_lock(ll->lock, &ctx);
519                         if (!err)
520                                 continue;
521
522                         ln = ll;
523                         list_for_each_entry_continue_reverse(ln, &locks, link)
524                                 ww_mutex_unlock(ln->lock);
525
526                         if (err != -EDEADLK) {
527                                 pr_err_once("stress (%s) failed with %d\n",
528                                             __func__, err);
529                                 break;
530                         }
531
532                         ww_mutex_lock_slow(ll->lock, &ctx);
533                         list_move(&ll->link, &locks); /* restarts iteration */
534                 }
535
536                 dummy_load(stress);
537                 list_for_each_entry(ll, &locks, link)
538                         ww_mutex_unlock(ll->lock);
539
540                 ww_acquire_fini(&ctx);
541         } while (!time_after(jiffies, stress->timeout));
542
543 out:
544         list_for_each_entry_safe(ll, ln, &locks, link)
545                 kfree(ll);
546         kfree(order);
547 }
548
549 static void stress_one_work(struct work_struct *work)
550 {
551         struct stress *stress = container_of(work, typeof(*stress), work);
552         const int nlocks = stress->nlocks;
553         struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks);
554         int err;
555
556         do {
557                 err = ww_mutex_lock(lock, NULL);
558                 if (!err) {
559                         dummy_load(stress);
560                         ww_mutex_unlock(lock);
561                 } else {
562                         pr_err_once("stress (%s) failed with %d\n",
563                                     __func__, err);
564                         break;
565                 }
566         } while (!time_after(jiffies, stress->timeout));
567 }
568
569 #define STRESS_INORDER BIT(0)
570 #define STRESS_REORDER BIT(1)
571 #define STRESS_ONE BIT(2)
572 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE)
573
574 static int stress(int nlocks, int nthreads, unsigned int flags)
575 {
576         struct ww_mutex *locks;
577         struct stress *stress_array;
578         int n, count;
579
580         locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
581         if (!locks)
582                 return -ENOMEM;
583
584         stress_array = kmalloc_array(nthreads, sizeof(*stress_array),
585                                      GFP_KERNEL);
586         if (!stress_array) {
587                 kfree(locks);
588                 return -ENOMEM;
589         }
590
591         for (n = 0; n < nlocks; n++)
592                 ww_mutex_init(&locks[n], &ww_class);
593
594         count = 0;
595         for (n = 0; nthreads; n++) {
596                 struct stress *stress;
597                 void (*fn)(struct work_struct *work);
598
599                 fn = NULL;
600                 switch (n & 3) {
601                 case 0:
602                         if (flags & STRESS_INORDER)
603                                 fn = stress_inorder_work;
604                         break;
605                 case 1:
606                         if (flags & STRESS_REORDER)
607                                 fn = stress_reorder_work;
608                         break;
609                 case 2:
610                         if (flags & STRESS_ONE)
611                                 fn = stress_one_work;
612                         break;
613                 }
614
615                 if (!fn)
616                         continue;
617
618                 stress = &stress_array[count++];
619
620                 INIT_WORK(&stress->work, fn);
621                 stress->locks = locks;
622                 stress->nlocks = nlocks;
623                 stress->timeout = jiffies + 2*HZ;
624
625                 queue_work(wq, &stress->work);
626                 nthreads--;
627         }
628
629         flush_workqueue(wq);
630
631         for (n = 0; n < nlocks; n++)
632                 ww_mutex_destroy(&locks[n]);
633         kfree(stress_array);
634         kfree(locks);
635
636         return 0;
637 }
638
639 static int __init test_ww_mutex_init(void)
640 {
641         int ncpus = num_online_cpus();
642         int ret, i;
643
644         printk(KERN_INFO "Beginning ww mutex selftests\n");
645
646         prandom_seed_state(&rng, get_random_u64());
647
648         wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
649         if (!wq)
650                 return -ENOMEM;
651
652         ret = test_mutex();
653         if (ret)
654                 return ret;
655
656         ret = test_aa(false);
657         if (ret)
658                 return ret;
659
660         ret = test_aa(true);
661         if (ret)
662                 return ret;
663
664         for (i = 0; i < 4; i++) {
665                 ret = test_abba(i & 1, i & 2);
666                 if (ret)
667                         return ret;
668         }
669
670         ret = test_cycle(ncpus);
671         if (ret)
672                 return ret;
673
674         ret = stress(16, 2*ncpus, STRESS_INORDER);
675         if (ret)
676                 return ret;
677
678         ret = stress(16, 2*ncpus, STRESS_REORDER);
679         if (ret)
680                 return ret;
681
682         ret = stress(2047, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
683         if (ret)
684                 return ret;
685
686         printk(KERN_INFO "All ww mutex selftests passed\n");
687         return 0;
688 }
689
690 static void __exit test_ww_mutex_exit(void)
691 {
692         destroy_workqueue(wq);
693 }
694
695 module_init(test_ww_mutex_init);
696 module_exit(test_ww_mutex_exit);
697
698 MODULE_LICENSE("GPL");
699 MODULE_AUTHOR("Intel Corporation");