1// SPDX-License-Identifier: MIT
2
3/*
4 * Copyright © 2019 Intel Corporation
5 */
6
7#include <linux/delay.h>
8#include <linux/dma-fence.h>
9#include <linux/dma-fence-chain.h>
10#include <linux/kernel.h>
11#include <linux/kthread.h>
12#include <linux/mm.h>
13#include <linux/sched/signal.h>
14#include <linux/slab.h>
15#include <linux/spinlock.h>
16#include <linux/random.h>
17
18#include "selftest.h"
19
20#define CHAIN_SZ (4 << 10)
21
22static struct kmem_cache *slab_fences;
23
24static inline struct mock_fence {
25	struct dma_fence base;
26	spinlock_t lock;
27} *to_mock_fence(struct dma_fence *f) {
28	return container_of(f, struct mock_fence, base);
29}
30
31static const char *mock_name(struct dma_fence *f)
32{
33	return "mock";
34}
35
36static void mock_fence_release(struct dma_fence *f)
37{
38	kmem_cache_free(slab_fences, to_mock_fence(f));
39}
40
41static const struct dma_fence_ops mock_ops = {
42	.get_driver_name = mock_name,
43	.get_timeline_name = mock_name,
44	.release = mock_fence_release,
45};
46
47static struct dma_fence *mock_fence(void)
48{
49	struct mock_fence *f;
50
51	f = kmem_cache_alloc(slab_fences, GFP_KERNEL);
52	if (!f)
53		return NULL;
54
55	spin_lock_init(&f->lock);
56	dma_fence_init(&f->base, &mock_ops, &f->lock, 0, 0);
57
58	return &f->base;
59}
60
61static inline struct mock_chain {
62	struct dma_fence_chain base;
63} *to_mock_chain(struct dma_fence *f) {
64	return container_of(f, struct mock_chain, base.base);
65}
66
67static struct dma_fence *mock_chain(struct dma_fence *prev,
68				    struct dma_fence *fence,
69				    u64 seqno)
70{
71	struct mock_chain *f;
72
73	f = kmalloc(sizeof(*f), GFP_KERNEL);
74	if (!f)
75		return NULL;
76
77	dma_fence_chain_init(&f->base,
78			     dma_fence_get(prev),
79			     dma_fence_get(fence),
80			     seqno);
81
82	return &f->base.base;
83}
84
85static int sanitycheck(void *arg)
86{
87	struct dma_fence *f, *chain;
88	int err = 0;
89
90	f = mock_fence();
91	if (!f)
92		return -ENOMEM;
93
94	chain = mock_chain(NULL, f, 1);
95	if (!chain)
96		err = -ENOMEM;
97
98	dma_fence_signal(f);
99	dma_fence_put(f);
100
101	dma_fence_put(chain);
102
103	return err;
104}
105
106struct fence_chains {
107	unsigned int chain_length;
108	struct dma_fence **fences;
109	struct dma_fence **chains;
110
111	struct dma_fence *tail;
112};
113
114static uint64_t seqno_inc(unsigned int i)
115{
116	return i + 1;
117}
118
119static int fence_chains_init(struct fence_chains *fc, unsigned int count,
120			     uint64_t (*seqno_fn)(unsigned int))
121{
122	unsigned int i;
123	int err = 0;
124
125	fc->chains = kvmalloc_array(count, sizeof(*fc->chains),
126				    GFP_KERNEL | __GFP_ZERO);
127	if (!fc->chains)
128		return -ENOMEM;
129
130	fc->fences = kvmalloc_array(count, sizeof(*fc->fences),
131				    GFP_KERNEL | __GFP_ZERO);
132	if (!fc->fences) {
133		err = -ENOMEM;
134		goto err_chains;
135	}
136
137	fc->tail = NULL;
138	for (i = 0; i < count; i++) {
139		fc->fences[i] = mock_fence();
140		if (!fc->fences[i]) {
141			err = -ENOMEM;
142			goto unwind;
143		}
144
145		fc->chains[i] = mock_chain(fc->tail,
146					   fc->fences[i],
147					   seqno_fn(i));
148		if (!fc->chains[i]) {
149			err = -ENOMEM;
150			goto unwind;
151		}
152
153		fc->tail = fc->chains[i];
154	}
155
156	fc->chain_length = i;
157	return 0;
158
159unwind:
160	for (i = 0; i < count; i++) {
161		dma_fence_put(fc->fences[i]);
162		dma_fence_put(fc->chains[i]);
163	}
164	kvfree(fc->fences);
165err_chains:
166	kvfree(fc->chains);
167	return err;
168}
169
170static void fence_chains_fini(struct fence_chains *fc)
171{
172	unsigned int i;
173
174	for (i = 0; i < fc->chain_length; i++) {
175		dma_fence_signal(fc->fences[i]);
176		dma_fence_put(fc->fences[i]);
177	}
178	kvfree(fc->fences);
179
180	for (i = 0; i < fc->chain_length; i++)
181		dma_fence_put(fc->chains[i]);
182	kvfree(fc->chains);
183}
184
185static int find_seqno(void *arg)
186{
187	struct fence_chains fc;
188	struct dma_fence *fence;
189	int err;
190	int i;
191
192	err = fence_chains_init(&fc, 64, seqno_inc);
193	if (err)
194		return err;
195
196	fence = dma_fence_get(fc.tail);
197	err = dma_fence_chain_find_seqno(&fence, 0);
198	dma_fence_put(fence);
199	if (err) {
200		pr_err("Reported %d for find_seqno(0)!\n", err);
201		goto err;
202	}
203
204	for (i = 0; i < fc.chain_length; i++) {
205		fence = dma_fence_get(fc.tail);
206		err = dma_fence_chain_find_seqno(&fence, i + 1);
207		dma_fence_put(fence);
208		if (err) {
209			pr_err("Reported %d for find_seqno(%d:%d)!\n",
210			       err, fc.chain_length + 1, i + 1);
211			goto err;
212		}
213		if (fence != fc.chains[i]) {
214			pr_err("Incorrect fence reported by find_seqno(%d:%d)\n",
215			       fc.chain_length + 1, i + 1);
216			err = -EINVAL;
217			goto err;
218		}
219
220		dma_fence_get(fence);
221		err = dma_fence_chain_find_seqno(&fence, i + 1);
222		dma_fence_put(fence);
223		if (err) {
224			pr_err("Error reported for finding self\n");
225			goto err;
226		}
227		if (fence != fc.chains[i]) {
228			pr_err("Incorrect fence reported by find self\n");
229			err = -EINVAL;
230			goto err;
231		}
232
233		dma_fence_get(fence);
234		err = dma_fence_chain_find_seqno(&fence, i + 2);
235		dma_fence_put(fence);
236		if (!err) {
237			pr_err("Error not reported for future fence: find_seqno(%d:%d)!\n",
238			       i + 1, i + 2);
239			err = -EINVAL;
240			goto err;
241		}
242
243		dma_fence_get(fence);
244		err = dma_fence_chain_find_seqno(&fence, i);
245		dma_fence_put(fence);
246		if (err) {
247			pr_err("Error reported for previous fence!\n");
248			goto err;
249		}
250		if (i > 0 && fence != fc.chains[i - 1]) {
251			pr_err("Incorrect fence reported by find_seqno(%d:%d)\n",
252			       i + 1, i);
253			err = -EINVAL;
254			goto err;
255		}
256	}
257
258err:
259	fence_chains_fini(&fc);
260	return err;
261}
262
263static int find_signaled(void *arg)
264{
265	struct fence_chains fc;
266	struct dma_fence *fence;
267	int err;
268
269	err = fence_chains_init(&fc, 2, seqno_inc);
270	if (err)
271		return err;
272
273	dma_fence_signal(fc.fences[0]);
274
275	fence = dma_fence_get(fc.tail);
276	err = dma_fence_chain_find_seqno(&fence, 1);
277	dma_fence_put(fence);
278	if (err) {
279		pr_err("Reported %d for find_seqno()!\n", err);
280		goto err;
281	}
282
283	if (fence && fence != fc.chains[0]) {
284		pr_err("Incorrect chain-fence.seqno:%lld reported for completed seqno:1\n",
285		       fence->seqno);
286
287		dma_fence_get(fence);
288		err = dma_fence_chain_find_seqno(&fence, 1);
289		dma_fence_put(fence);
290		if (err)
291			pr_err("Reported %d for finding self!\n", err);
292
293		err = -EINVAL;
294	}
295
296err:
297	fence_chains_fini(&fc);
298	return err;
299}
300
301static int find_out_of_order(void *arg)
302{
303	struct fence_chains fc;
304	struct dma_fence *fence;
305	int err;
306
307	err = fence_chains_init(&fc, 3, seqno_inc);
308	if (err)
309		return err;
310
311	dma_fence_signal(fc.fences[1]);
312
313	fence = dma_fence_get(fc.tail);
314	err = dma_fence_chain_find_seqno(&fence, 2);
315	dma_fence_put(fence);
316	if (err) {
317		pr_err("Reported %d for find_seqno()!\n", err);
318		goto err;
319	}
320
321	/*
322	 * We signaled the middle fence (2) of the 1-2-3 chain. The behavior
323	 * of the dma-fence-chain is to make us wait for all the fences up to
324	 * the point we want. Since fence 1 is still not signaled, this what
325	 * we should get as fence to wait upon (fence 2 being garbage
326	 * collected during the traversal of the chain).
327	 */
328	if (fence != fc.chains[0]) {
329		pr_err("Incorrect chain-fence.seqno:%lld reported for completed seqno:2\n",
330		       fence ? fence->seqno : 0);
331
332		err = -EINVAL;
333	}
334
335err:
336	fence_chains_fini(&fc);
337	return err;
338}
339
340static uint64_t seqno_inc2(unsigned int i)
341{
342	return 2 * i + 2;
343}
344
345static int find_gap(void *arg)
346{
347	struct fence_chains fc;
348	struct dma_fence *fence;
349	int err;
350	int i;
351
352	err = fence_chains_init(&fc, 64, seqno_inc2);
353	if (err)
354		return err;
355
356	for (i = 0; i < fc.chain_length; i++) {
357		fence = dma_fence_get(fc.tail);
358		err = dma_fence_chain_find_seqno(&fence, 2 * i + 1);
359		dma_fence_put(fence);
360		if (err) {
361			pr_err("Reported %d for find_seqno(%d:%d)!\n",
362			       err, fc.chain_length + 1, 2 * i + 1);
363			goto err;
364		}
365		if (fence != fc.chains[i]) {
366			pr_err("Incorrect fence.seqno:%lld reported by find_seqno(%d:%d)\n",
367			       fence->seqno,
368			       fc.chain_length + 1,
369			       2 * i + 1);
370			err = -EINVAL;
371			goto err;
372		}
373
374		dma_fence_get(fence);
375		err = dma_fence_chain_find_seqno(&fence, 2 * i + 2);
376		dma_fence_put(fence);
377		if (err) {
378			pr_err("Error reported for finding self\n");
379			goto err;
380		}
381		if (fence != fc.chains[i]) {
382			pr_err("Incorrect fence reported by find self\n");
383			err = -EINVAL;
384			goto err;
385		}
386	}
387
388err:
389	fence_chains_fini(&fc);
390	return err;
391}
392
393struct find_race {
394	struct fence_chains fc;
395	atomic_t children;
396};
397
398static int __find_race(void *arg)
399{
400	struct find_race *data = arg;
401	int err = 0;
402
403	while (!kthread_should_stop()) {
404		struct dma_fence *fence = dma_fence_get(data->fc.tail);
405		int seqno;
406
407		seqno = prandom_u32_max(data->fc.chain_length) + 1;
408
409		err = dma_fence_chain_find_seqno(&fence, seqno);
410		if (err) {
411			pr_err("Failed to find fence seqno:%d\n",
412			       seqno);
413			dma_fence_put(fence);
414			break;
415		}
416		if (!fence)
417			goto signal;
418
419		/*
420		 * We can only find ourselves if we are on fence we were
421		 * looking for.
422		 */
423		if (fence->seqno == seqno) {
424			err = dma_fence_chain_find_seqno(&fence, seqno);
425			if (err) {
426				pr_err("Reported an invalid fence for find-self:%d\n",
427				       seqno);
428				dma_fence_put(fence);
429				break;
430			}
431		}
432
433		dma_fence_put(fence);
434
435signal:
436		seqno = prandom_u32_max(data->fc.chain_length - 1);
437		dma_fence_signal(data->fc.fences[seqno]);
438		cond_resched();
439	}
440
441	if (atomic_dec_and_test(&data->children))
442		wake_up_var(&data->children);
443	return err;
444}
445
446static int find_race(void *arg)
447{
448	struct find_race data;
449	int ncpus = num_online_cpus();
450	struct task_struct **threads;
451	unsigned long count;
452	int err;
453	int i;
454
455	err = fence_chains_init(&data.fc, CHAIN_SZ, seqno_inc);
456	if (err)
457		return err;
458
459	threads = kmalloc_array(ncpus, sizeof(*threads), GFP_KERNEL);
460	if (!threads) {
461		err = -ENOMEM;
462		goto err;
463	}
464
465	atomic_set(&data.children, 0);
466	for (i = 0; i < ncpus; i++) {
467		threads[i] = kthread_run(__find_race, &data, "dmabuf/%d", i);
468		if (IS_ERR(threads[i])) {
469			ncpus = i;
470			break;
471		}
472		atomic_inc(&data.children);
473		get_task_struct(threads[i]);
474	}
475
476	wait_var_event_timeout(&data.children,
477			       !atomic_read(&data.children),
478			       5 * HZ);
479
480	for (i = 0; i < ncpus; i++) {
481		int ret;
482
483		ret = kthread_stop(threads[i]);
484		if (ret && !err)
485			err = ret;
486		put_task_struct(threads[i]);
487	}
488	kfree(threads);
489
490	count = 0;
491	for (i = 0; i < data.fc.chain_length; i++)
492		if (dma_fence_is_signaled(data.fc.fences[i]))
493			count++;
494	pr_info("Completed %lu cycles\n", count);
495
496err:
497	fence_chains_fini(&data.fc);
498	return err;
499}
500
501static int signal_forward(void *arg)
502{
503	struct fence_chains fc;
504	int err;
505	int i;
506
507	err = fence_chains_init(&fc, 64, seqno_inc);
508	if (err)
509		return err;
510
511	for (i = 0; i < fc.chain_length; i++) {
512		dma_fence_signal(fc.fences[i]);
513
514		if (!dma_fence_is_signaled(fc.chains[i])) {
515			pr_err("chain[%d] not signaled!\n", i);
516			err = -EINVAL;
517			goto err;
518		}
519
520		if (i + 1 < fc.chain_length &&
521		    dma_fence_is_signaled(fc.chains[i + 1])) {
522			pr_err("chain[%d] is signaled!\n", i);
523			err = -EINVAL;
524			goto err;
525		}
526	}
527
528err:
529	fence_chains_fini(&fc);
530	return err;
531}
532
533static int signal_backward(void *arg)
534{
535	struct fence_chains fc;
536	int err;
537	int i;
538
539	err = fence_chains_init(&fc, 64, seqno_inc);
540	if (err)
541		return err;
542
543	for (i = fc.chain_length; i--; ) {
544		dma_fence_signal(fc.fences[i]);
545
546		if (i > 0 && dma_fence_is_signaled(fc.chains[i])) {
547			pr_err("chain[%d] is signaled!\n", i);
548			err = -EINVAL;
549			goto err;
550		}
551	}
552
553	for (i = 0; i < fc.chain_length; i++) {
554		if (!dma_fence_is_signaled(fc.chains[i])) {
555			pr_err("chain[%d] was not signaled!\n", i);
556			err = -EINVAL;
557			goto err;
558		}
559	}
560
561err:
562	fence_chains_fini(&fc);
563	return err;
564}
565
566static int __wait_fence_chains(void *arg)
567{
568	struct fence_chains *fc = arg;
569
570	if (dma_fence_wait(fc->tail, false))
571		return -EIO;
572
573	return 0;
574}
575
576static int wait_forward(void *arg)
577{
578	struct fence_chains fc;
579	struct task_struct *tsk;
580	int err;
581	int i;
582
583	err = fence_chains_init(&fc, CHAIN_SZ, seqno_inc);
584	if (err)
585		return err;
586
587	tsk = kthread_run(__wait_fence_chains, &fc, "dmabuf/wait");
588	if (IS_ERR(tsk)) {
589		err = PTR_ERR(tsk);
590		goto err;
591	}
592	get_task_struct(tsk);
593	yield_to(tsk, true);
594
595	for (i = 0; i < fc.chain_length; i++)
596		dma_fence_signal(fc.fences[i]);
597
598	err = kthread_stop(tsk);
599	put_task_struct(tsk);
600
601err:
602	fence_chains_fini(&fc);
603	return err;
604}
605
606static int wait_backward(void *arg)
607{
608	struct fence_chains fc;
609	struct task_struct *tsk;
610	int err;
611	int i;
612
613	err = fence_chains_init(&fc, CHAIN_SZ, seqno_inc);
614	if (err)
615		return err;
616
617	tsk = kthread_run(__wait_fence_chains, &fc, "dmabuf/wait");
618	if (IS_ERR(tsk)) {
619		err = PTR_ERR(tsk);
620		goto err;
621	}
622	get_task_struct(tsk);
623	yield_to(tsk, true);
624
625	for (i = fc.chain_length; i--; )
626		dma_fence_signal(fc.fences[i]);
627
628	err = kthread_stop(tsk);
629	put_task_struct(tsk);
630
631err:
632	fence_chains_fini(&fc);
633	return err;
634}
635
636static void randomise_fences(struct fence_chains *fc)
637{
638	unsigned int count = fc->chain_length;
639
640	/* Fisher-Yates shuffle courtesy of Knuth */
641	while (--count) {
642		unsigned int swp;
643
644		swp = prandom_u32_max(count + 1);
645		if (swp == count)
646			continue;
647
648		swap(fc->fences[count], fc->fences[swp]);
649	}
650}
651
652static int wait_random(void *arg)
653{
654	struct fence_chains fc;
655	struct task_struct *tsk;
656	int err;
657	int i;
658
659	err = fence_chains_init(&fc, CHAIN_SZ, seqno_inc);
660	if (err)
661		return err;
662
663	randomise_fences(&fc);
664
665	tsk = kthread_run(__wait_fence_chains, &fc, "dmabuf/wait");
666	if (IS_ERR(tsk)) {
667		err = PTR_ERR(tsk);
668		goto err;
669	}
670	get_task_struct(tsk);
671	yield_to(tsk, true);
672
673	for (i = 0; i < fc.chain_length; i++)
674		dma_fence_signal(fc.fences[i]);
675
676	err = kthread_stop(tsk);
677	put_task_struct(tsk);
678
679err:
680	fence_chains_fini(&fc);
681	return err;
682}
683
684int dma_fence_chain(void)
685{
686	static const struct subtest tests[] = {
687		SUBTEST(sanitycheck),
688		SUBTEST(find_seqno),
689		SUBTEST(find_signaled),
690		SUBTEST(find_out_of_order),
691		SUBTEST(find_gap),
692		SUBTEST(find_race),
693		SUBTEST(signal_forward),
694		SUBTEST(signal_backward),
695		SUBTEST(wait_forward),
696		SUBTEST(wait_backward),
697		SUBTEST(wait_random),
698	};
699	int ret;
700
701	pr_info("sizeof(dma_fence_chain)=%zu\n",
702		sizeof(struct dma_fence_chain));
703
704	slab_fences = KMEM_CACHE(mock_fence,
705				 SLAB_TYPESAFE_BY_RCU |
706				 SLAB_HWCACHE_ALIGN);
707	if (!slab_fences)
708		return -ENOMEM;
709
710	ret = subtests(tests, NULL);
711
712	kmem_cache_destroy(slab_fences);
713	return ret;
714}
715