1 /*
2 * Copyright © 2016 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 *
23 */
24
25 #include "../i915_selftest.h"
26 #include "i915_random.h"
27
28 #include "mock_gem_device.h"
29 #include "mock_engine.h"
30
check_rbtree(struct intel_engine_cs * engine,const unsigned long * bitmap,const struct intel_wait * waiters,const int count)31 static int check_rbtree(struct intel_engine_cs *engine,
32 const unsigned long *bitmap,
33 const struct intel_wait *waiters,
34 const int count)
35 {
36 struct intel_breadcrumbs *b = &engine->breadcrumbs;
37 struct rb_node *rb;
38 int n;
39
40 if (&b->irq_wait->node != rb_first(&b->waiters)) {
41 pr_err("First waiter does not match first element of wait-tree\n");
42 return -EINVAL;
43 }
44
45 n = find_first_bit(bitmap, count);
46 for (rb = rb_first(&b->waiters); rb; rb = rb_next(rb)) {
47 struct intel_wait *w = container_of(rb, typeof(*w), node);
48 int idx = w - waiters;
49
50 if (!test_bit(idx, bitmap)) {
51 pr_err("waiter[%d, seqno=%d] removed but still in wait-tree\n",
52 idx, w->seqno);
53 return -EINVAL;
54 }
55
56 if (n != idx) {
57 pr_err("waiter[%d, seqno=%d] does not match expected next element in tree [%d]\n",
58 idx, w->seqno, n);
59 return -EINVAL;
60 }
61
62 n = find_next_bit(bitmap, count, n + 1);
63 }
64
65 return 0;
66 }
67
check_completion(struct intel_engine_cs * engine,const unsigned long * bitmap,const struct intel_wait * waiters,const int count)68 static int check_completion(struct intel_engine_cs *engine,
69 const unsigned long *bitmap,
70 const struct intel_wait *waiters,
71 const int count)
72 {
73 int n;
74
75 for (n = 0; n < count; n++) {
76 if (intel_wait_complete(&waiters[n]) != !!test_bit(n, bitmap))
77 continue;
78
79 pr_err("waiter[%d, seqno=%d] is %s, but expected %s\n",
80 n, waiters[n].seqno,
81 intel_wait_complete(&waiters[n]) ? "complete" : "active",
82 test_bit(n, bitmap) ? "active" : "complete");
83 return -EINVAL;
84 }
85
86 return 0;
87 }
88
check_rbtree_empty(struct intel_engine_cs * engine)89 static int check_rbtree_empty(struct intel_engine_cs *engine)
90 {
91 struct intel_breadcrumbs *b = &engine->breadcrumbs;
92
93 if (b->irq_wait) {
94 pr_err("Empty breadcrumbs still has a waiter\n");
95 return -EINVAL;
96 }
97
98 if (!RB_EMPTY_ROOT(&b->waiters)) {
99 pr_err("Empty breadcrumbs, but wait-tree not empty\n");
100 return -EINVAL;
101 }
102
103 return 0;
104 }
105
igt_random_insert_remove(void * arg)106 static int igt_random_insert_remove(void *arg)
107 {
108 const u32 seqno_bias = 0x1000;
109 I915_RND_STATE(prng);
110 struct intel_engine_cs *engine = arg;
111 struct intel_wait *waiters;
112 const int count = 4096;
113 unsigned int *order;
114 unsigned long *bitmap;
115 int err = -ENOMEM;
116 int n;
117
118 mock_engine_reset(engine);
119
120 waiters = kvmalloc_array(count, sizeof(*waiters), GFP_KERNEL);
121 if (!waiters)
122 goto out_engines;
123
124 bitmap = kcalloc(DIV_ROUND_UP(count, BITS_PER_LONG), sizeof(*bitmap),
125 GFP_KERNEL);
126 if (!bitmap)
127 goto out_waiters;
128
129 order = i915_random_order(count, &prng);
130 if (!order)
131 goto out_bitmap;
132
133 for (n = 0; n < count; n++)
134 intel_wait_init_for_seqno(&waiters[n], seqno_bias + n);
135
136 err = check_rbtree(engine, bitmap, waiters, count);
137 if (err)
138 goto out_order;
139
140 /* Add and remove waiters into the rbtree in random order. At each
141 * step, we verify that the rbtree is correctly ordered.
142 */
143 for (n = 0; n < count; n++) {
144 int i = order[n];
145
146 intel_engine_add_wait(engine, &waiters[i]);
147 __set_bit(i, bitmap);
148
149 err = check_rbtree(engine, bitmap, waiters, count);
150 if (err)
151 goto out_order;
152 }
153
154 i915_random_reorder(order, count, &prng);
155 for (n = 0; n < count; n++) {
156 int i = order[n];
157
158 intel_engine_remove_wait(engine, &waiters[i]);
159 __clear_bit(i, bitmap);
160
161 err = check_rbtree(engine, bitmap, waiters, count);
162 if (err)
163 goto out_order;
164 }
165
166 err = check_rbtree_empty(engine);
167 out_order:
168 kfree(order);
169 out_bitmap:
170 kfree(bitmap);
171 out_waiters:
172 kvfree(waiters);
173 out_engines:
174 mock_engine_flush(engine);
175 return err;
176 }
177
igt_insert_complete(void * arg)178 static int igt_insert_complete(void *arg)
179 {
180 const u32 seqno_bias = 0x1000;
181 struct intel_engine_cs *engine = arg;
182 struct intel_wait *waiters;
183 const int count = 4096;
184 unsigned long *bitmap;
185 int err = -ENOMEM;
186 int n, m;
187
188 mock_engine_reset(engine);
189
190 waiters = kvmalloc_array(count, sizeof(*waiters), GFP_KERNEL);
191 if (!waiters)
192 goto out_engines;
193
194 bitmap = kcalloc(DIV_ROUND_UP(count, BITS_PER_LONG), sizeof(*bitmap),
195 GFP_KERNEL);
196 if (!bitmap)
197 goto out_waiters;
198
199 for (n = 0; n < count; n++) {
200 intel_wait_init_for_seqno(&waiters[n], n + seqno_bias);
201 intel_engine_add_wait(engine, &waiters[n]);
202 __set_bit(n, bitmap);
203 }
204 err = check_rbtree(engine, bitmap, waiters, count);
205 if (err)
206 goto out_bitmap;
207
208 /* On each step, we advance the seqno so that several waiters are then
209 * complete (we increase the seqno by increasingly larger values to
210 * retire more and more waiters at once). All retired waiters should
211 * be woken and removed from the rbtree, and so that we check.
212 */
213 for (n = 0; n < count; n = m) {
214 int seqno = 2 * n;
215
216 GEM_BUG_ON(find_first_bit(bitmap, count) != n);
217
218 if (intel_wait_complete(&waiters[n])) {
219 pr_err("waiter[%d, seqno=%d] completed too early\n",
220 n, waiters[n].seqno);
221 err = -EINVAL;
222 goto out_bitmap;
223 }
224
225 /* complete the following waiters */
226 mock_seqno_advance(engine, seqno + seqno_bias);
227 for (m = n; m <= seqno; m++) {
228 if (m == count)
229 break;
230
231 GEM_BUG_ON(!test_bit(m, bitmap));
232 __clear_bit(m, bitmap);
233 }
234
235 intel_engine_remove_wait(engine, &waiters[n]);
236 RB_CLEAR_NODE(&waiters[n].node);
237
238 err = check_rbtree(engine, bitmap, waiters, count);
239 if (err) {
240 pr_err("rbtree corrupt after seqno advance to %d\n",
241 seqno + seqno_bias);
242 goto out_bitmap;
243 }
244
245 err = check_completion(engine, bitmap, waiters, count);
246 if (err) {
247 pr_err("completions after seqno advance to %d failed\n",
248 seqno + seqno_bias);
249 goto out_bitmap;
250 }
251 }
252
253 err = check_rbtree_empty(engine);
254 out_bitmap:
255 kfree(bitmap);
256 out_waiters:
257 kvfree(waiters);
258 out_engines:
259 mock_engine_flush(engine);
260 return err;
261 }
262
263 struct igt_wakeup {
264 struct task_struct *tsk;
265 atomic_t *ready, *set, *done;
266 struct intel_engine_cs *engine;
267 unsigned long flags;
268 #define STOP 0
269 #define IDLE 1
270 wait_queue_head_t *wq;
271 u32 seqno;
272 };
273
wait_for_ready(struct igt_wakeup * w)274 static bool wait_for_ready(struct igt_wakeup *w)
275 {
276 DEFINE_WAIT(ready);
277
278 set_bit(IDLE, &w->flags);
279 if (atomic_dec_and_test(w->done))
280 wake_up_var(w->done);
281
282 if (test_bit(STOP, &w->flags))
283 goto out;
284
285 for (;;) {
286 prepare_to_wait(w->wq, &ready, TASK_INTERRUPTIBLE);
287 if (atomic_read(w->ready) == 0)
288 break;
289
290 schedule();
291 }
292 finish_wait(w->wq, &ready);
293
294 out:
295 clear_bit(IDLE, &w->flags);
296 if (atomic_dec_and_test(w->set))
297 wake_up_var(w->set);
298
299 return !test_bit(STOP, &w->flags);
300 }
301
igt_wakeup_thread(void * arg)302 static int igt_wakeup_thread(void *arg)
303 {
304 struct igt_wakeup *w = arg;
305 struct intel_wait wait;
306
307 while (wait_for_ready(w)) {
308 GEM_BUG_ON(kthread_should_stop());
309
310 intel_wait_init_for_seqno(&wait, w->seqno);
311 intel_engine_add_wait(w->engine, &wait);
312 for (;;) {
313 set_current_state(TASK_UNINTERRUPTIBLE);
314 if (i915_seqno_passed(intel_engine_get_seqno(w->engine),
315 w->seqno))
316 break;
317
318 if (test_bit(STOP, &w->flags)) /* emergency escape */
319 break;
320
321 schedule();
322 }
323 intel_engine_remove_wait(w->engine, &wait);
324 __set_current_state(TASK_RUNNING);
325 }
326
327 return 0;
328 }
329
igt_wake_all_sync(atomic_t * ready,atomic_t * set,atomic_t * done,wait_queue_head_t * wq,int count)330 static void igt_wake_all_sync(atomic_t *ready,
331 atomic_t *set,
332 atomic_t *done,
333 wait_queue_head_t *wq,
334 int count)
335 {
336 atomic_set(set, count);
337 atomic_set(ready, 0);
338 wake_up_all(wq);
339
340 wait_var_event(set, !atomic_read(set));
341 atomic_set(ready, count);
342 atomic_set(done, count);
343 }
344
igt_wakeup(void * arg)345 static int igt_wakeup(void *arg)
346 {
347 I915_RND_STATE(prng);
348 struct intel_engine_cs *engine = arg;
349 struct igt_wakeup *waiters;
350 DECLARE_WAIT_QUEUE_HEAD_ONSTACK(wq);
351 const int count = 4096;
352 const u32 max_seqno = count / 4;
353 atomic_t ready, set, done;
354 int err = -ENOMEM;
355 int n, step;
356
357 mock_engine_reset(engine);
358
359 waiters = kvmalloc_array(count, sizeof(*waiters), GFP_KERNEL);
360 if (!waiters)
361 goto out_engines;
362
363 /* Create a large number of threads, each waiting on a random seqno.
364 * Multiple waiters will be waiting for the same seqno.
365 */
366 atomic_set(&ready, count);
367 for (n = 0; n < count; n++) {
368 waiters[n].wq = &wq;
369 waiters[n].ready = &ready;
370 waiters[n].set = &set;
371 waiters[n].done = &done;
372 waiters[n].engine = engine;
373 waiters[n].flags = BIT(IDLE);
374
375 waiters[n].tsk = kthread_run(igt_wakeup_thread, &waiters[n],
376 "i915/igt:%d", n);
377 if (IS_ERR(waiters[n].tsk))
378 goto out_waiters;
379
380 get_task_struct(waiters[n].tsk);
381 }
382
383 for (step = 1; step <= max_seqno; step <<= 1) {
384 u32 seqno;
385
386 /* The waiter threads start paused as we assign them a random
387 * seqno and reset the engine. Once the engine is reset,
388 * we signal that the threads may begin their wait upon their
389 * seqno.
390 */
391 for (n = 0; n < count; n++) {
392 GEM_BUG_ON(!test_bit(IDLE, &waiters[n].flags));
393 waiters[n].seqno =
394 1 + prandom_u32_state(&prng) % max_seqno;
395 }
396 mock_seqno_advance(engine, 0);
397 igt_wake_all_sync(&ready, &set, &done, &wq, count);
398
399 /* Simulate the GPU doing chunks of work, with one or more
400 * seqno appearing to finish at the same time. A random number
401 * of threads will be waiting upon the update and hopefully be
402 * woken.
403 */
404 for (seqno = 1; seqno <= max_seqno + step; seqno += step) {
405 usleep_range(50, 500);
406 mock_seqno_advance(engine, seqno);
407 }
408 GEM_BUG_ON(intel_engine_get_seqno(engine) < 1 + max_seqno);
409
410 /* With the seqno now beyond any of the waiting threads, they
411 * should all be woken, see that they are complete and signal
412 * that they are ready for the next test. We wait until all
413 * threads are complete and waiting for us (i.e. not a seqno).
414 */
415 if (!wait_var_event_timeout(&done,
416 !atomic_read(&done), 10 * HZ)) {
417 pr_err("Timed out waiting for %d remaining waiters\n",
418 atomic_read(&done));
419 err = -ETIMEDOUT;
420 break;
421 }
422
423 err = check_rbtree_empty(engine);
424 if (err)
425 break;
426 }
427
428 out_waiters:
429 for (n = 0; n < count; n++) {
430 if (IS_ERR(waiters[n].tsk))
431 break;
432
433 set_bit(STOP, &waiters[n].flags);
434 }
435 mock_seqno_advance(engine, INT_MAX); /* wakeup any broken waiters */
436 igt_wake_all_sync(&ready, &set, &done, &wq, n);
437
438 for (n = 0; n < count; n++) {
439 if (IS_ERR(waiters[n].tsk))
440 break;
441
442 kthread_stop(waiters[n].tsk);
443 put_task_struct(waiters[n].tsk);
444 }
445
446 kvfree(waiters);
447 out_engines:
448 mock_engine_flush(engine);
449 return err;
450 }
451
intel_breadcrumbs_mock_selftests(void)452 int intel_breadcrumbs_mock_selftests(void)
453 {
454 static const struct i915_subtest tests[] = {
455 SUBTEST(igt_random_insert_remove),
456 SUBTEST(igt_insert_complete),
457 SUBTEST(igt_wakeup),
458 };
459 struct drm_i915_private *i915;
460 int err;
461
462 i915 = mock_gem_device();
463 if (!i915)
464 return -ENOMEM;
465
466 err = i915_subtests(tests, i915->engine[RCS]);
467 drm_dev_put(&i915->drm);
468
469 return err;
470 }
471
