1/*
2 * Copyright © 2017 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
28static char *
29__sync_print(struct i915_syncmap *p,
30 char *buf, unsigned long *sz,
31 unsigned int depth,
32 unsigned int last,
33 unsigned int idx)
34{
35 unsigned long len;
36 unsigned int i, X;
37
38 if (depth) {
39 unsigned int d;
40
41 for (d = 0; d < depth - 1; d++) {
42 if (last & BIT(depth - d - 1))
43 len = scnprintf(buf, size: *sz, fmt: "| ");
44 else
45 len = scnprintf(buf, size: *sz, fmt: " ");
46 buf += len;
47 *sz -= len;
48 }
49 len = scnprintf(buf, size: *sz, fmt: "%x-> ", idx);
50 buf += len;
51 *sz -= len;
52 }
53
54 /* We mark bits after the prefix as "X" */
55 len = scnprintf(buf, size: *sz, fmt: "0x%016llx", p->prefix << p->height << SHIFT);
56 buf += len;
57 *sz -= len;
58 X = (p->height + SHIFT) / 4;
59 scnprintf(buf: buf - X, size: *sz + X, fmt: "%*s", X, "XXXXXXXXXXXXXXXXX");
60
61 if (!p->height) {
62 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
63 len = scnprintf(buf, size: *sz, fmt: " %x:%x,",
64 i, __sync_seqno(p)[i]);
65 buf += len;
66 *sz -= len;
67 }
68 buf -= 1;
69 *sz += 1;
70 }
71
72 len = scnprintf(buf, size: *sz, fmt: "\n");
73 buf += len;
74 *sz -= len;
75
76 if (p->height) {
77 for_each_set_bit(i, (unsigned long *)&p->bitmap, KSYNCMAP) {
78 buf = __sync_print(p: __sync_child(p)[i], buf, sz,
79 depth: depth + 1,
80 last: last << 1 | ((p->bitmap >> (i + 1)) ? 1 : 0),
81 idx: i);
82 }
83 }
84
85 return buf;
86}
87
88static bool
89i915_syncmap_print_to_buf(struct i915_syncmap *p, char *buf, unsigned long sz)
90{
91 if (!p)
92 return false;
93
94 while (p->parent)
95 p = p->parent;
96
97 __sync_print(p, buf, sz: &sz, depth: 0, last: 1, idx: 0);
98 return true;
99}
100
101static int check_syncmap_free(struct i915_syncmap **sync)
102{
103 i915_syncmap_free(root: sync);
104 if (*sync) {
105 pr_err("sync not cleared after free\n");
106 return -EINVAL;
107 }
108
109 return 0;
110}
111
112static int dump_syncmap(struct i915_syncmap *sync, int err)
113{
114 char *buf;
115
116 if (!err)
117 return check_syncmap_free(sync: &sync);
118
119 buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
120 if (!buf)
121 goto skip;
122
123 if (i915_syncmap_print_to_buf(p: sync, buf, PAGE_SIZE))
124 pr_err("%s", buf);
125
126 kfree(objp: buf);
127
128skip:
129 i915_syncmap_free(root: &sync);
130 return err;
131}
132
133static int igt_syncmap_init(void *arg)
134{
135 struct i915_syncmap *sync = (void *)~0ul;
136
137 /*
138 * Cursory check that we can initialise a random pointer and transform
139 * it into the root pointer of a syncmap.
140 */
141
142 i915_syncmap_init(root: &sync);
143 return check_syncmap_free(sync: &sync);
144}
145
146static int check_seqno(struct i915_syncmap *leaf, unsigned int idx, u32 seqno)
147{
148 if (leaf->height) {
149 pr_err("%s: not a leaf, height is %d\n",
150 __func__, leaf->height);
151 return -EINVAL;
152 }
153
154 if (__sync_seqno(p: leaf)[idx] != seqno) {
155 pr_err("%s: seqno[%d], found %x, expected %x\n",
156 __func__, idx, __sync_seqno(leaf)[idx], seqno);
157 return -EINVAL;
158 }
159
160 return 0;
161}
162
163static int check_one(struct i915_syncmap **sync, u64 context, u32 seqno)
164{
165 int err;
166
167 err = i915_syncmap_set(root: sync, id: context, seqno);
168 if (err)
169 return err;
170
171 if ((*sync)->height) {
172 pr_err("Inserting first context=%llx did not return leaf (height=%d, prefix=%llx\n",
173 context, (*sync)->height, (*sync)->prefix);
174 return -EINVAL;
175 }
176
177 if ((*sync)->parent) {
178 pr_err("Inserting first context=%llx created branches!\n",
179 context);
180 return -EINVAL;
181 }
182
183 if (hweight32((*sync)->bitmap) != 1) {
184 pr_err("First bitmap does not contain a single entry, found %x (count=%d)!\n",
185 (*sync)->bitmap, hweight32((*sync)->bitmap));
186 return -EINVAL;
187 }
188
189 err = check_seqno(leaf: (*sync), ilog2((*sync)->bitmap), seqno);
190 if (err)
191 return err;
192
193 if (!i915_syncmap_is_later(root: sync, id: context, seqno)) {
194 pr_err("Lookup of first context=%llx/seqno=%x failed!\n",
195 context, seqno);
196 return -EINVAL;
197 }
198
199 return 0;
200}
201
202static int igt_syncmap_one(void *arg)
203{
204 I915_RND_STATE(prng);
205 IGT_TIMEOUT(end_time);
206 struct i915_syncmap *sync;
207 unsigned long max = 1;
208 int err;
209
210 /*
211 * Check that inserting a new id, creates a leaf and only that leaf.
212 */
213
214 i915_syncmap_init(root: &sync);
215
216 do {
217 u64 context = i915_prandom_u64_state(rnd: &prng);
218 unsigned long loop;
219
220 err = check_syncmap_free(sync: &sync);
221 if (err)
222 goto out;
223
224 for (loop = 0; loop <= max; loop++) {
225 err = check_one(sync: &sync, context,
226 seqno: prandom_u32_state(state: &prng));
227 if (err)
228 goto out;
229 }
230 max++;
231 } while (!__igt_timeout(timeout: end_time, NULL));
232 pr_debug("%s: Completed %lu single insertions\n",
233 __func__, max * (max - 1) / 2);
234out:
235 return dump_syncmap(sync, err);
236}
237
238static int check_leaf(struct i915_syncmap **sync, u64 context, u32 seqno)
239{
240 int err;
241
242 err = i915_syncmap_set(root: sync, id: context, seqno);
243 if (err)
244 return err;
245
246 if ((*sync)->height) {
247 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
248 context, (*sync)->height, (*sync)->prefix);
249 return -EINVAL;
250 }
251
252 if (hweight32((*sync)->bitmap) != 1) {
253 pr_err("First entry into leaf (context=%llx) does not contain a single entry, found %x (count=%d)!\n",
254 context, (*sync)->bitmap, hweight32((*sync)->bitmap));
255 return -EINVAL;
256 }
257
258 err = check_seqno(leaf: (*sync), ilog2((*sync)->bitmap), seqno);
259 if (err)
260 return err;
261
262 if (!i915_syncmap_is_later(root: sync, id: context, seqno)) {
263 pr_err("Lookup of first entry context=%llx/seqno=%x failed!\n",
264 context, seqno);
265 return -EINVAL;
266 }
267
268 return 0;
269}
270
271static int igt_syncmap_join_above(void *arg)
272{
273 struct i915_syncmap *sync;
274 unsigned int pass, order;
275 int err;
276
277 i915_syncmap_init(root: &sync);
278
279 /*
280 * When we have a new id that doesn't fit inside the existing tree,
281 * we need to add a new layer above.
282 *
283 * 1: 0x00000001
284 * 2: 0x00000010
285 * 3: 0x00000100
286 * 4: 0x00001000
287 * ...
288 * Each pass the common prefix shrinks and we have to insert a join.
289 * Each join will only contain two branches, the latest of which
290 * is always a leaf.
291 *
292 * If we then reuse the same set of contexts, we expect to build an
293 * identical tree.
294 */
295 for (pass = 0; pass < 3; pass++) {
296 for (order = 0; order < 64; order += SHIFT) {
297 u64 context = BIT_ULL(order);
298 struct i915_syncmap *join;
299
300 err = check_leaf(sync: &sync, context, seqno: 0);
301 if (err)
302 goto out;
303
304 join = sync->parent;
305 if (!join) /* very first insert will have no parents */
306 continue;
307
308 if (!join->height) {
309 pr_err("Parent with no height!\n");
310 err = -EINVAL;
311 goto out;
312 }
313
314 if (hweight32(join->bitmap) != 2) {
315 pr_err("Join does not have 2 children: %x (%d)\n",
316 join->bitmap, hweight32(join->bitmap));
317 err = -EINVAL;
318 goto out;
319 }
320
321 if (__sync_child(p: join)[__sync_branch_idx(p: join, id: context)] != sync) {
322 pr_err("Leaf misplaced in parent!\n");
323 err = -EINVAL;
324 goto out;
325 }
326 }
327 }
328out:
329 return dump_syncmap(sync, err);
330}
331
332static int igt_syncmap_join_below(void *arg)
333{
334 struct i915_syncmap *sync;
335 unsigned int step, order, idx;
336 int err = -ENODEV;
337
338 i915_syncmap_init(root: &sync);
339
340 /*
341 * Check that we can split a compacted branch by replacing it with
342 * a join.
343 */
344 for (step = 0; step < KSYNCMAP; step++) {
345 for (order = 64 - SHIFT; order > 0; order -= SHIFT) {
346 u64 context = step * BIT_ULL(order);
347
348 err = i915_syncmap_set(root: &sync, id: context, seqno: 0);
349 if (err)
350 goto out;
351
352 if (sync->height) {
353 pr_err("Inserting context=%llx (order=%d, step=%d) did not return leaf (height=%d, prefix=%llx\n",
354 context, order, step, sync->height, sync->prefix);
355 err = -EINVAL;
356 goto out;
357 }
358 }
359 }
360
361 for (step = 0; step < KSYNCMAP; step++) {
362 for (order = SHIFT; order < 64; order += SHIFT) {
363 u64 context = step * BIT_ULL(order);
364
365 if (!i915_syncmap_is_later(root: &sync, id: context, seqno: 0)) {
366 pr_err("1: context %llx (order=%d, step=%d) not found\n",
367 context, order, step);
368 err = -EINVAL;
369 goto out;
370 }
371
372 for (idx = 1; idx < KSYNCMAP; idx++) {
373 if (i915_syncmap_is_later(root: &sync, id: context + idx, seqno: 0)) {
374 pr_err("1: context %llx (order=%d, step=%d) should not exist\n",
375 context + idx, order, step);
376 err = -EINVAL;
377 goto out;
378 }
379 }
380 }
381 }
382
383 for (order = SHIFT; order < 64; order += SHIFT) {
384 for (step = 0; step < KSYNCMAP; step++) {
385 u64 context = step * BIT_ULL(order);
386
387 if (!i915_syncmap_is_later(root: &sync, id: context, seqno: 0)) {
388 pr_err("2: context %llx (order=%d, step=%d) not found\n",
389 context, order, step);
390 err = -EINVAL;
391 goto out;
392 }
393 }
394 }
395
396out:
397 return dump_syncmap(sync, err);
398}
399
400static int igt_syncmap_neighbours(void *arg)
401{
402 I915_RND_STATE(prng);
403 IGT_TIMEOUT(end_time);
404 struct i915_syncmap *sync;
405 int err = -ENODEV;
406
407 /*
408 * Each leaf holds KSYNCMAP seqno. Check that when we create KSYNCMAP
409 * neighbouring ids, they all fit into the same leaf.
410 */
411
412 i915_syncmap_init(root: &sync);
413 do {
414 u64 context = i915_prandom_u64_state(rnd: &prng) & ~MASK;
415 unsigned int idx;
416
417 if (i915_syncmap_is_later(root: &sync, id: context, seqno: 0)) /* Skip repeats */
418 continue;
419
420 for (idx = 0; idx < KSYNCMAP; idx++) {
421 err = i915_syncmap_set(root: &sync, id: context + idx, seqno: 0);
422 if (err)
423 goto out;
424
425 if (sync->height) {
426 pr_err("Inserting context=%llx did not return leaf (height=%d, prefix=%llx\n",
427 context, sync->height, sync->prefix);
428 err = -EINVAL;
429 goto out;
430 }
431
432 if (sync->bitmap != BIT(idx + 1) - 1) {
433 pr_err("Inserting neighbouring context=0x%llx+%d, did not fit into the same leaf bitmap=%x (%d), expected %lx (%d)\n",
434 context, idx,
435 sync->bitmap, hweight32(sync->bitmap),
436 BIT(idx + 1) - 1, idx + 1);
437 err = -EINVAL;
438 goto out;
439 }
440 }
441 } while (!__igt_timeout(timeout: end_time, NULL));
442out:
443 return dump_syncmap(sync, err);
444}
445
446static int igt_syncmap_compact(void *arg)
447{
448 struct i915_syncmap *sync;
449 unsigned int idx, order;
450 int err = -ENODEV;
451
452 i915_syncmap_init(root: &sync);
453
454 /*
455 * The syncmap are "space efficient" compressed radix trees - any
456 * branch with only one child is skipped and replaced by the child.
457 *
458 * If we construct a tree with ids that are neighbouring at a non-zero
459 * height, we form a join but each child of that join is directly a
460 * leaf holding the single id.
461 */
462 for (order = SHIFT; order < 64; order += SHIFT) {
463 err = check_syncmap_free(sync: &sync);
464 if (err)
465 goto out;
466
467 /* Create neighbours in the parent */
468 for (idx = 0; idx < KSYNCMAP; idx++) {
469 u64 context = idx * BIT_ULL(order) + idx;
470
471 err = i915_syncmap_set(root: &sync, id: context, seqno: 0);
472 if (err)
473 goto out;
474
475 if (sync->height) {
476 pr_err("Inserting context=%llx (order=%d, idx=%d) did not return leaf (height=%d, prefix=%llx\n",
477 context, order, idx,
478 sync->height, sync->prefix);
479 err = -EINVAL;
480 goto out;
481 }
482 }
483
484 sync = sync->parent;
485 if (sync->parent) {
486 pr_err("Parent (join) of last leaf was not the sync!\n");
487 err = -EINVAL;
488 goto out;
489 }
490
491 if (sync->height != order) {
492 pr_err("Join does not have the expected height, found %d, expected %d\n",
493 sync->height, order);
494 err = -EINVAL;
495 goto out;
496 }
497
498 if (sync->bitmap != BIT(KSYNCMAP) - 1) {
499 pr_err("Join is not full!, found %x (%d) expected %lx (%d)\n",
500 sync->bitmap, hweight32(sync->bitmap),
501 BIT(KSYNCMAP) - 1, KSYNCMAP);
502 err = -EINVAL;
503 goto out;
504 }
505
506 /* Each of our children should be a leaf */
507 for (idx = 0; idx < KSYNCMAP; idx++) {
508 struct i915_syncmap *leaf = __sync_child(p: sync)[idx];
509
510 if (leaf->height) {
511 pr_err("Child %d is a not leaf!\n", idx);
512 err = -EINVAL;
513 goto out;
514 }
515
516 if (leaf->parent != sync) {
517 pr_err("Child %d is not attached to us!\n",
518 idx);
519 err = -EINVAL;
520 goto out;
521 }
522
523 if (!is_power_of_2(n: leaf->bitmap)) {
524 pr_err("Child %d holds more than one id, found %x (%d)\n",
525 idx, leaf->bitmap, hweight32(leaf->bitmap));
526 err = -EINVAL;
527 goto out;
528 }
529
530 if (leaf->bitmap != BIT(idx)) {
531 pr_err("Child %d has wrong seqno idx, found %d, expected %d\n",
532 idx, ilog2(leaf->bitmap), idx);
533 err = -EINVAL;
534 goto out;
535 }
536 }
537 }
538out:
539 return dump_syncmap(sync, err);
540}
541
542static int igt_syncmap_random(void *arg)
543{
544 I915_RND_STATE(prng);
545 IGT_TIMEOUT(end_time);
546 struct i915_syncmap *sync;
547 unsigned long count, phase, i;
548 u32 seqno;
549 int err;
550
551 i915_syncmap_init(root: &sync);
552
553 /*
554 * Having tried to test the individual operations within i915_syncmap,
555 * run a smoketest exploring the entire u64 space with random
556 * insertions.
557 */
558
559 count = 0;
560 phase = jiffies + HZ/100 + 1;
561 do {
562 u64 context = i915_prandom_u64_state(rnd: &prng);
563
564 err = i915_syncmap_set(root: &sync, id: context, seqno: 0);
565 if (err)
566 goto out;
567
568 count++;
569 } while (!time_after(jiffies, phase));
570 seqno = 0;
571
572 phase = 0;
573 do {
574 I915_RND_STATE(ctx);
575 u32 last_seqno = seqno;
576 bool expect;
577
578 seqno = prandom_u32_state(state: &prng);
579 expect = seqno_later(a: last_seqno, b: seqno);
580
581 for (i = 0; i < count; i++) {
582 u64 context = i915_prandom_u64_state(rnd: &ctx);
583
584 if (i915_syncmap_is_later(root: &sync, id: context, seqno) != expect) {
585 pr_err("context=%llu, last=%u this=%u did not match expectation (%d)\n",
586 context, last_seqno, seqno, expect);
587 err = -EINVAL;
588 goto out;
589 }
590
591 err = i915_syncmap_set(root: &sync, id: context, seqno);
592 if (err)
593 goto out;
594 }
595
596 phase++;
597 } while (!__igt_timeout(timeout: end_time, NULL));
598 pr_debug("Completed %lu passes, each of %lu contexts\n", phase, count);
599out:
600 return dump_syncmap(sync, err);
601}
602
603int i915_syncmap_mock_selftests(void)
604{
605 static const struct i915_subtest tests[] = {
606 SUBTEST(igt_syncmap_init),
607 SUBTEST(igt_syncmap_one),
608 SUBTEST(igt_syncmap_join_above),
609 SUBTEST(igt_syncmap_join_below),
610 SUBTEST(igt_syncmap_neighbours),
611 SUBTEST(igt_syncmap_compact),
612 SUBTEST(igt_syncmap_random),
613 };
614
615 return i915_subtests(tests, NULL);
616}
617

source code of linux/drivers/gpu/drm/i915/selftests/i915_syncmap.c