~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/locking/test-ww_mutex.c

Version: ~ [ linux-5.5-rc1 ] ~ [ linux-5.4.2 ] ~ [ linux-5.3.15 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.88 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.158 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.206 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.206 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.78 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp